Graafiteoriassa graafia kutsutaan sointuiseksi , jos jokaisella sen syklillä , jossa on vähintään neljä reunaa, on sointu (reuna, joka yhdistää syklin kaksi kärkeä, mutta ei ole osa sitä).
Vastaava määritelmä on, jos jollakin syklillä ilman sointuja on enintään kolme reunaa. Toisin sanoen sointukaavio on kaavio, jossa ei ole generoituja syklejä, joiden pituus on yli kolme.
Sointukuvaajat ovat täydellisten graafien osajoukko . Niitä kutsutaan joskus myös syklisesti jäykiksi graafiksi [1] tai kolmiomittaiseksi graafiksi . (Jälkimmäistä termiä käytetään joskus virheellisesti tasokolmioinnissa. Katso maksimaaliset tasokaaviot .) [2]
Täydellinen poissulkemisjärjestys graafissa on graafin kärkien järjestys siten, että jokaiselle pisteelle v , v ja v : n naapurit , jotka ovat v :n jälkeen järjestyksessä, muodostavat klikkin . Graafi on sointu silloin ja vain, jos sillä on täydellinen poissulkemisjärjestys [3]
Rose, Lucker ja Tarjan (1976) [4] (katso myös Habib, McConnell, Paul, Vienneno (2000) [5] ) osoittivat, että sointugraafin täydellinen eliminointijärjestys voidaan löytää tehokkaasti käyttämällä algoritmia, joka tunnetaan nimellä leksikografinen leveys- ensimmäinen haku . Tämä algoritmi jakaa graafin kärjet joukkojen sarjaksi. Aluksi sarja koostuu yhdestä joukosta, joka sisältää kaikki kärjet. Silmukassa oleva algoritmi valitsee kärjen v sekvenssin vanhimmasta joukosta, joka sisältää vielä valitsemattomat kärjet, ja jakaa sekvenssin jokaisen joukon S kahdeksi pienemmäksi - toinen koostuu S :n kärjen v naapureista , toinen sisältää kaikki loput kärjet. Kun jakoprosessi suoritetaan kaikille pisteille, kaikki sekvenssin joukot sisältävät kukin yhden kärjen ja muodostavat sekvenssin käänteisen täydelliseen eliminointijärjestykseen.
Koska sekä leksikografinen leveyshaku että tarkistukset, onko järjestys täydellinen poikkeus, voidaan tehdä lineaarisessa ajassa, on mahdollista tunnistaa sointukuvaaja lineaarisessa ajassa. Sointugraafin sandwich -tehtävä on NP-täydellinen [6] , kun taas sointugraafin testigrafiikkatehtävä on polynomiajan monimutkaisuus [7] .
Sointugraafin kaikkien täydellisten poissulkemisjärjestysten joukkoa voidaan pitää antimatroidin perussanoina . Chandran ym . [8] käyttivät tätä yhteyttä antimatroideihin osana algoritmia laskeakseen tehokkaasti kaikki täydelliset poissulkemisjärjestykset tietylle sointukaaviolle.
Toinen täydellisen eliminointijärjestyksen sovellus on sointukuvaajan maksimiklikin löytäminen polynomiajassa , kun taas yleisillä graafilla sama ongelma on NP-täydellinen (sointugraafissa voi olla vain lineaarisesti monta suurinta klikkausta , kun taas ei-sointukuvaajilla voi olla eksponentiaalisesti monet niistä). Saadakseen luettelon kaikista sointugraafin suurimmista klikkeistä riittää, kun löytää täydellinen eliminointijärjestys, muodostaa jokaiselle pisteelle v klikki kaikista naapuripisteistä järjestyksessä v :n jälkeen ja tarkistaa, onko tuloksena saatu klikki suurin.
Suurin klikki, jolla on maksimikoko, on maksimiklikki, ja koska sointukuvaajat ovat täydellisiä, tämän klikkin koko on yhtä suuri kuin sointukuvaajan kromaattinen luku . Sointukuvaajat ovat hyvin järjestettävissä - optimaalinen väritys saadaan käyttämällä ahneella väritysalgoritmilla , jolloin kärjet otetaan käänteisessä järjestyksessä täydelliseen eliminointiin. [9]
Missä tahansa graafissa kärkipisteiden erotin on joukko pisteitä, joiden poistaminen tekee jäljellä olevan graafin irti. Erotin on minimaalinen, jos se ei sisällä osajoukkoa, joka on myös erotin. Diracin lauseen [1] mukaan sointukäyrät ovat kaavioita, joissa jokainen minimierotin on klikki. Dirac käytti tätä ominaisuutta todistaakseen, että sointukaaviot ovat täydellisiä .
Sointukaavioiden perhe voidaan määritellä joukoksi kaavioita, joiden kärjet voidaan jakaa kolmeen ei-tyhjään osajoukkoon A , S ja B siten, että A ∪ S ja S ∪ B muodostavat kumpikin sointugeneroituja aligraafia , S on klikki, eikä A: ta ja B :tä yhdistäviä reunoja ole. _ Nämä ovat siis kaavioita, jotka mahdollistavat rekursiivisen osioinnin pienempiin aligraafiin käyttämällä klikkejä. Tästä syystä sointukaavioita kutsutaan joskus hajotettaviksi kaavioiksi . [kymmenen]
Toinen sointugraafien [11] ominaisuus käyttää puita ja niiden alipuita.
Puun alipuujoukosta voidaan määrittää alipuugraafi - leikkausgraafi , jonka kukin kärki vastaa alipuuta ja reuna yhdistää kaksi alipuuta, jos niillä on yksi tai useampi yhteinen reuna. Gavril osoitti, että alipuukaaviot ovat täsmälleen sointukaavioita.
Sointugraafien esittäminen alipuun leikkausgraafina muodostaa graafin jaottelun puiksi , joiden puun leveys on yhtä pienempi kuin graafin suurimman klikkin koko. Minkä tahansa graafin G hajottamista puiksi voidaan pitää graafin G esityksenä sointugraafin aligraafina. Graafin jakaminen puiksi on myös liittopuu luotettavuuden etenemisalgoritmissa .
Intervallikaaviot ovat alipuun leikkauskaavioita , puiden erikoistapaus. Näin ollen intervallikaaviot ovat sointukaavioiden alaryhmä.
Jaetut graafit ovat itse sointuja ja ne täydentävät sointukaavioita. Bender, Richmond ja Wormald (1985) [12] osoittivat, että kun n:llä on taipumus äärettömään, n:n pisteen jakattujen sointugraafien murto-osa pyrkii yhteen.
Ptolemaios-graafit ovat kaavioita, jotka ovat sekä sointu- että etäisyysperiytyviä . Kvasikynnysgraafit ovat Ptolemaioksen graafien alaluokka, jotka ovat sekä sointu- että kografia . Lohkograafit ovat toinen Ptolemaioksen graafien alaluokka, jossa kahdella suurimmalla klikkauksella on enintään yksi yhteinen kärki. Erikoistapaus ovat myllyt , joilla on sama kärkipiste mille tahansa klikkiparille.
Tarkkaan sointukuvaajat ovat kaavioita, jotka ovat sointuja eivätkä sisällä n-aurinkoa ( n ≥ 3) generoituina aligraafina.
K-puut ovat sointukaavioita, joiden suurimmat klikkit ja suurimmat klikkien erottimet ovat kaikki samankokoisia. [13] Apollonius-graafit ovat sointumaksimaalisia tasokaavioita tai vastaavasti tasomaisia 3-puita. [13] Maksimaaliset ulkotasograafit ovat 2-puun alaluokka ja siksi myös sointuja.
Sointukuvaajat ovat tunnettujen täydellisten graafien alaluokka . Muita sointukaavioiden yliluokkia ovat heikot sointukuvaajat, graafit ilman parittomat reikiä ja graafit ilman parillisia reikiä . Itse asiassa sointukuvaajat ovat täsmälleen kaavioita, sekä ilman parillisia reikiä että ilman parittomia reikiä (katso reikä graafiteoriassa).
Mikä tahansa sointugraafi on supistettu , eli graafi, jossa mikä tahansa kehäsykli on kolmio, koska kehäsyklit ovat generoidun jakson erikoistapaus. Supistetut graafit voidaan muodostaa sointukaavioiden ja maksimaalisten sointukaavioiden klikkausummilla . Siten supistetut kuvaajat sisältävät maksimaaliset tasograafit . [neljätoista]