Välinpitämätön kaavio

Välinpitämätön graafi on suuntaamaton graafi , joka on muodostettu antamalla jokaiselle pisteelle reaaliluku ja yhdistämällä kaksi kärkeä reunalla, kun niiden lukumäärät eroavat enintään yhdellä [1] . Välinpitämättömät graafit ovat myös kaavioita yksikkösegmenttien joukkojen tai intervallien leikkauspisteistä, joilla on tietty upotusominaisuus (mikään intervalli ei sisällä muita). Näiden kahden tyyppisten intervalliesitysten perusteella näitä kaavioita kutsutaan myös yksikkösegmenttikaavioiksi tai oikeiksi intervallikaavioiksi . Välinpitämättömät graafit muodostavat intervallikaavioiden alaluokan .

Vastaavat kuvaukset

Äärilliset välinpitämättömät graafit voidaan kuvata vastaavasti

Äärettömille kaavioille jotkin näistä määritelmistä voidaan antaa eri kaavioilla.

Ominaisuudet

Koska välinpitämättömät kaaviot ovat intervallikaavioiden erikoistapaus , välinpitämättömillä kaavioilla on kaikki intervallikaavioiden ominaisuudet. Erityisesti ne ovat sointukaavioiden ja täydellisten graafien erikoistapaus . Nämä kaaviot ovat myös ympyräkaavioiden erikoistapaus , mikä ei pidä paikkaansa yleisten intervallikaavioiden kohdalla.

Erdős - Rényi satunnaisten graafien mallissa graafi, jonka kärjessä on huomattavasti vähemmän reunoja , on suurella todennäköisyydellä välinpitämätön graafi, kun taas graafit, joissa on huomattavasti suurempi määrä reunoja , eivät ole välinpitämättömiä graafia, jolla on suuri todennäköisyys [9] .

Mielivaltaisen graafin nauhan leveys on yksi pienempi kuinsisältävän indiferentin graafin suurimman klikkin koko, joka on valittu minimoimaan suurimman klikkin koko [10] . Tämä ominaisuus muodostaa yhtäläisyyksiä, jotka ovat samanlaisia ​​kuin yhteys polunleveyden ja intervallikaavioiden välillä sekä puunleveyden ja sointukaavioiden välillä . Heikompi käsite leveydestä, klikin leveys , voi olla mielivaltaisen suuri välinpitämättömillä kaavioilla [11] . Jokaisella oikealla välinpitämättömien graafien alaluokilla, jotka eivät ole suljettuja generoitujen aligraafien suhteen, on kuitenkin rajoitettu klikin leveys [12] .

Mikä tahansa kytketty indifferentti graafi sisältää Hamiltonin polun [13] . Välinpitämättömällä graafilla on Hamiltonin graafi silloin ja vain, jos se on kaksinkertaisesti yhdistetty [14] .

Välinpitämättömät graafit täyttävät rekonstruktiooletuksen — ne määritellään yksiselitteisesti niiden kärjestä poistettujen aligraafien avulla [15] .

Algoritmit

Kuten moniulotteisten yksikkölevykaavioiden kohdalla, on mahdollista muuntaa joukko pisteitä niiden välinpitämättömäksi kuvaajaksi tai joukko yksikkösegmenttejä niiden yksikkösegmenttien kuvaajaksi lineaarisessa ajassa , mitattuna tuloskaavion koosta. Algoritmi pyöristää pisteet (tai välien keskipisteet) lähimpään pienempään kokonaislukuun, käyttää hash-taulukkoa löytääkseen kaikki pisteparit, joiden pyöristetyt arvot eroavat enintään yhdellä ( kiinteän säteen lähimmän naapurin ongelma ), ja valitsee parit tuloksena oleva lista, jonka pyöristämättömät arvot ovat enintään yksi toisistaan ​​[16] .

Voidaan testata, onko tietty graafi lineaarisessa ajassa välinpitämätön käyttämällä PQ-puita graafin intervalliesitysten muodostamiseen, ja sitten testata, täyttääkö tästä esityksestä johdettu kärkijärjestys indifferentin graafin ominaisuudet [4] . Välinpitämättömien graafien tunnistusalgoritmi voidaan myös perustaa sointukuvaajan tunnistusalgoritmeihin [14] . Jotkut vaihtoehtoiset lineaariset ajantunnistusalgoritmit perustuvat leveys-ensimmäiseen hakuun tai leksikografiseen leveyshakuun , eikä välinpitämättömien graafien ja intervallikaavioiden väliseen suhteeseen [17] [18] [19] [20] .

Kun pisteet on lajiteltu niiden numeeristen arvojen mukaan, jotka kuvaavat välinpitämätöntä kuvaajaa (tai yksikkösegmenttien sarjan mukaan intervallisävyssä), samaa järjestystä voidaan käyttää näiden kuvaajien optimaalisen värityksen löytämiseen lyhimmän polun ongelman ratkaisemiseksi. , Hamiltonin polkujen rakentaminen ja suurimmat vastaavuudet lineaarisessa ajassa [4] . Hamiltonin sykli voidaan löytää oikeasta intervalliesitysgraafista ajassa [13] , mutta jos graafi on syöte ongelmaan, sama ongelma voidaan ratkaista lineaarisessa ajassa, joka voidaan yleistää intervallikaavioiksi [21] [ 22] .

Määrätty väritys pysyy NP-täydellisenä , vaikka se rajoittuu välinpitämättömiin kuvaajiin [23] . Se on kuitenkin kiinteä-parametrisesti ratkaistava , jos parametroidaan syötevärien kokonaismäärällä [12] .

Sovellukset

Matemaattisessa psykologiassa välinpitämättömät graafit syntyvät hyödyllisyysfunktioista skaalaamalla funktiota niin, että yksi yksikkö edustaa niin pientä hyötyeroa, että yksikköä voidaan pitää yksilön kannalta merkityksettömänä. Tässä sovelluksessa elementiparit, joiden apuohjelmat ovat riittävän suuria, voidaan järjestää osittain suhteellisen hyödyllisyysjärjestyksen mukaan, jolloin saadaan puolijärjestys [1] [24] .

Bioinformatiikassa tehtävää lisätä värillinen graafi oikein väritettyyn yksikkösegmenttien kuvaajaan voidaan mallintaa väärien negatiivisten DNA - genomikokoonpanojen havaitsemista fragmenteista [25] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 Roberts, 1969 , s. 139-146.
  2. ↑ 1 2 Bogart, West, 1999 , s. 21–23.
  3. ↑ Wegner, 1967 .
  4. ↑ 1 2 3 Looges, Olariu, 1993 , s. 15-25.
  5. ↑ Jackowski, 1992 , s. 103–109.
  6. ↑ 1 2 Gutierrez, Oubina, 1996 , s. 199-205.
  7. ↑ Mertzios, 2008 , s. 332-337.
  8. ↑ 1 2 Brandstädt, Hundt, Mancini, Wagner, 2010 , s. 897–910.
  9. ↑ Cohen, 1982 , s. 21–24.
  10. ↑ Kaplan, Shamir, 1996 , s. 540–561.
  11. ↑ Golumbic, Rotics, 1999 , s. 5-17.
  12. ↑ 1 2 Lozin, 2008 , s. 871–882.
  13. ↑ 1 2 Bertossi, 1983 , s. 97–101.
  14. ↑ 1 2 Panda, Das, 2003 , s. 153-161.
  15. ↑ von Rimscha, 1983 , s. 283-291.
  16. ↑ Bentley, Stanat, Williams, 1977 , s. 209–212.
  17. ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995 , s. 99–104.
  18. ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995 , s. 179-184.
  19. ↑ Corneil, 2004 , s. 371-379.
  20. ↑ Helvetti, Huang, 2004 , s. 554–570.
  21. ↑ Keil, 1985 , s. 201–206.
  22. ↑ Ibarra, 2009 , s. 1105–1108.
  23. ↑ Marx, 2006 , s. 995–1002.
  24. ↑ Roberts, 1970 , s. 243-258.
  25. ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009 .

Kirjallisuus

Linkit