Tarkkaan sointukaavio

Suuntaamatonta graafia G kutsutaan tiukasti sointuiseksi , jos se on sointu ja jokaisella parillisen pituisella ( ) syklillä G :ssä on pariton sointu , eli reuna, joka yhdistää kaksi syklin kärkeä parittoman etäisyyden (>1) päässä toisistaan [1] .

Kuvaus

Tiukasti sointukaavioita kuvataan kiellettyjen graafien avulla graafiksi, jotka eivät sisällä yli kolmen pituista generoitua sykliä tai n - aurinkoa ( ) generoituna osagraafina [2] [3] [4] . n - Aurinko on sointugraafi, jossa on 2n kärkeä jaettu kahteen osajoukkoon ja siten, että jokaisella W : n kärjellä w i on täsmälleen kaksi naapuria, u i ja . n -Aurinko ei voi olla tiukasti sointu, koska syklissä ... ei ole parittomia sointuja.

Tarkkaan sointukaavioita voidaan kuvata graafeiksi, joilla on tiukka täydellinen eliminointijärjestys, sellainen huippupistejärjestys, että minkä tahansa myöhemmin järjestyksen tullen kärjen naapurit muodostavat klikkin ja sellaisiksi, että mille tahansa , jos järjestyksen i - piste on k : nnen ja l :nnen pisteen vierekkäin ja j- : nnet ja k - nnet pisteet ovat vierekkäisiä, niin sekä j- että l -pisteen tulee olla vierekkäin [3] [5] .

Graafi on tiukasti sointu, jos ja vain jos jollakin sen generoiduista osagraafista on yksinkertainen kärkipiste, toisin sanoen kärki, jonka naapurit on järjestetty lineaarisesti inkluusiojärjestyksen mukaan [3] [6] . Graafi on myös tiukasti sointu, jos ja vain jos se on sointu ja missä tahansa syklissä, jonka pituus on viisi tai enemmän, on 2-sointuinen kolmio, eli kolmio, joka muodostuu kahdesta sointeesta ja syklin reunasta [7] .

Graafi on tiukasti sointu, jos ja vain jos jokin sen generoiduista aligraafista on kaksoiskordaaligraafi [8] .

Tarkkaan sointugraafit voidaan kuvata kokonaisten aligraafien lukumäärällä, joihin jokin reuna kuuluu [9] . Toinen kuvaus on annettu De Carian ja McKeen artikkelissa [10] .

Tunnustus

On mahdollista määrittää, onko graafi polynomiajassa tiukasti sointu, etsimällä ja poistamalla toistuvasti yksinkertaista kärkeä. Jos tämä prosessi eliminoi kaikki graafin kärjet, graafin on oltava ehdottomasti sointu. Muuten prosessi ei löydä aligraafia ilman yksinkertaista kärkeä, ja tässä tapauksessa alkuperäinen graafi ei voi olla tiukasti sointu. Tiukasti sointugraafissa järjestystä, jossa kärkipisteet poistetaan tässä prosessissa, kutsutaan tiukasti täydelliseksi eliminointijärjestykseksi [3] .

Tunnetaan vaihtoehtoisia algoritmeja, jotka voivat määrittää, onko graafi ehdottomasti sointu, ja jos on, rakentaa tiukan täydellisen eliminointijärjestyksen tehokkaammin ajassa graafille, jossa on n kärkeä ja m reunaa [11] [12] [13] .

Alaluokat

Tärkeä alaluokka (perustuu fylogiaan ) on k - lehtiasteiden luokka , eli graafit, jotka muodostetaan puun lehdistä yhdistämällä kaksi lehteä reunalla, jos etäisyys puussa ei ole suurempi kuin k . Lehden aste on graafi, joka on k -lehtiaste jollekin k :lle . Koska tiukasti sointukaavioiden asteet ovat tiukasti sointuja ja puut tiukasti sointuja, tästä seuraa, että lehtien asteet ovat tiukasti sointuja. Ne muodostavat oman alaluokkansa vahvasti sointuja kuvaavista graafista, joka puolestaan ​​sisältää klusterigraafit 2-arkin potenssina [14] . Toinen tärkeä tiukasti sointukaavioiden alaluokka ovat intervallikaaviot . Branstedt, Hudt, Mancini ja Wagner [15] osoittivat, että intervallikaaviot ja suurempi luokka suunnattuja juuripolkuja ovat lehtitehoja.

Algoritmiset ongelmat

Koska vahvasti sointujen graafit ovat sekä sointu- että kaksoissointuja , erilaisia ​​NP-täydellisiä tehtäviä, kuten riippumaton joukkotehtävä , klikkitehtävä , väritys , klikkipeiteongelma , hallitseva joukko ja Steinerin minimaalipuuongelma, voidaan ratkaista tehokkaasti vahvasti sointujen graafien kohdalla. Graafisen isomorfismin ongelma on GI-täydellinen [16] tiukasti sointukaavioille [17] . Hamiltonin syklien etsiminen on edelleen NP-täydellinen ongelma tiukasti sointujakograafille [18] .

Muistiinpanot

  1. ↑ Brandstädt, Le, Spinrad, 1999 , s. 43, määritelmä 3.4.1.
  2. ↑ Chang, 1982 .
  3. ↑ 1 2 3 4 Farber, 1983 .
  4. ↑ Brandstädt, Le, Spinrad, 1999 , s. 112, Lause 7.2.1.
  5. ↑ Brandstädt, Le, Spinrad, 1999 , s. 77, Lause 5.5.1.
  6. ↑ Brandstädt, Le, Spinrad, 1999 , s. 78, Lause 5.5.2.
  7. ↑ Dahlhaus, Manuel, Miller, 1998 .
  8. ↑ Brandstädt, Dragan, Chepoi, Voloshin, 1998 , s. 444, seuraus 3.
  9. ↑ McKee, 1999 .
  10. ↑ De Caria, McKee, 2014 .
  11. ↑ Lubiw, 1987 .
  12. ↑ Paige, Tarjan, 1987 .
  13. ↑ Spinrad, 1993 .
  14. ↑ Nishimura, Ragde, Thilikos, 2002 .
  15. ↑ Brandstädt, Hundt, Mancini, Wagner, 2010 .
  16. ↑ Artikkelissa esitellään uusi täydellisyysluokka - Graph Isomorphism täydellisyys
  17. ↑ Uehara, Toda, Nagoya, 2005 .
  18. ↑ Müller, 1996 .

Kirjallisuus