Triviaalisen täydellinen kaavio

Triviaalisen täydellinen graafi  on graafi, jolla on ominaisuus, että sen jokaisessa generoidussa aligraafissa suurimman ( koon mukaan) riippumattoman joukon koko on yhtä suuri kuin maksimiklikkien lukumäärä [1] [2] . Triviaalisen täydelliset graafit tutki ensin Volk [3] [4] , mutta nimen antoi Golumbik [2] . Golumbik kirjoitti, että "tämä nimi valittiin tällaisten kuvaajien täydellisyyden todistamisen triviaalisuuden vuoksi ." Triviaalisen täydelliset graafit tunnetaan myös puuvertailugraafina [3] [4] , puiden vertailukelpoisuuden graafina [ 5] ja kvasikynnysgraafina [6] .

Vastaavat kuvaukset

Triviaalisti täydellisillä kaavioilla on useita muita vastaavia kuvauksia:

• Ne ovat puiden vertailukaavioita järjestusteoriasta . Eli olkoon  T osittaisjärjestys siten , että mille tahansa t ∈ T :lle joukko { s ∈ T  : s < t } on hyvin järjestetty suhteessa < ja T :llä on pienin alkio r . Tällöin kertaluvun T vertailtavuusgraafi on triviaalisti täydellinen ja mikä tahansa triviaali täydellinen graafi voidaan muodostaa tällä tavalla [7] [8] .
• Ne ovat kaavioita, jotka eivät sisällä P 4 -polkua tai C 4 -sykliä generoituina alikaavioina [ 7] [9] [10]
• Ne ovat kaavioita, joissa jokainen yhdistetty generoitu osagraafi sisältää universaalin kärjen [11] .
• Ne ovat kaavioita, joita voidaan pitää sisäkkäisten välien joukon intervallikaavioina . Aukkojen joukolla on sisäkkäisyysominaisuus, jos ne eivät leikkaa kahdessa joukossa olevaa aukkoa tai toinen niistä sisältyy toiseen [12] .
• Ne ovat kaavioita, jotka ovat sekä sointukaavioita että kografeja [13] [14] . Tämä seuraa kuvauksesta sointugraafit graafit ilman generoituja jaksoja, joiden pituus on neljä tai enemmän ja cographs graafit ilman generoituja polkuja neljällä kärjellä ( P4 ).
• Ne ovat kaavioita, jotka ovat sekä kopio- että intervallikaavioita [13] [14] .
• Ne ovat graafeja, jotka voidaan muodostaa aloittaen graafista, jossa on yksi kärki, käyttämällä kahta operaatiota - kahden pienemmän triviaalisen täydellisen graafin disjunktoitua liittoa ja lisäämällä uusi kärki pienempien triviaalisen täydellisen graafin kaikkien kärkien viereen [6] [15] . Nämä toiminnot vastaavat uuden metsän muodostamista yhdistämällä kahta pienempää metsää epäyhtenäisesti ja puun muodostamista liittämällä uusi juuri kaikkien metsän puiden juuriin.
• Ne ovat kaavioita, joissa missä tahansa reunassa uv kärkien u ja v lähialueet (mukaan lukien itse u ja v ) on sisäkkäin - yhden naapuruston on oltava toisen naapuri [14] .
• Ne ovat permutaatiokaavioita , jotka on määritelty pinoon lajiteltujen permutaatioiden perusteella [16] .
• Ne ovat kaavioita, joiden ominaisuus on, että kussakin sen generoidussa aligraafissa klikkauksen kattavuus on yhtä suuri kuin maksimiklikkien lukumäärä [17] .
• Ne ovat kaavioita, joilla on ominaisuus, että jokaisessa sen generoidussa aligraafissa klikkin numero on yhtä suuri kuin Grandin pseudoluku [17] .
• Ne ovat kaavioita, joiden ominaisuus on, että kunkin sen generoidun aligraafin kromaattinen luku on yhtä suuri kuin pseudo Grandi -luku [17] .

Aiheeseen liittyvät graafiluokat

Triviaalisti täydellisten graafien vastaavista kuvauksista seuraa, että mikä tahansa triviaalisti täydellinen graafi on myös cograph , sointu , Ptolemaios , intervalli ja täydellinen graafi .

Kynnysgraafit  ovat täsmälleen niitä graafisia, jotka ovat sekä triviaalisti täydellisiä että ovat triviaalisti täydellisten graafien (triviaalisti täydellisten graafien) komplementteja [18] [19] .

Myllyt ovat triviaalisti täydellisiä.

Tunnustus

Chu [20] kuvaa yksinkertaisen lineaarisen aikaalgoritmin triviaalisti täydellisten graafien tunnistamiseksi leksikografisen leveyshaun perusteella . Kun LexBFS-algoritmi poistaa v :n jonon ensimmäisestä joukosta, algoritmi tarkistaa, että kaikki v :n jäljellä olevat naapurit ovat samassa joukossa. Jos ei, yksi kielletyistä generoiduista osagraafista voidaan rakentaa v :stä . Jos tarkistus onnistuu kaikille v :lle, graafi on triviaalisti täydellinen. Algoritmia voidaan muokata testaamaan lineaarisessa ajassa, onko graafi triviaalisen täydellisen graafin komplementti .

Sen määrittäminen, tuleeko yleisestä graafista k reunan poistamisen jälkeen triviaalisti täydellinen graafi, on NP-täydellinen tehtävä [21] , ratkaistava kiinteällä parametrilla [22] ja se voidaan ratkaista ajassa O(2,45 k (m+n) ) [ 23] .

Muistiinpanot

1. ↑ Brandstädt, Le, Spinrad, 1999 , s. 34 määritelmä 2.6.2.
2. ↑ 1 2 Golumbic, 1978 .
3. ↑ 12 Wolk , 1962 .
4. ↑ 12 Wolk , 1965 .
5. ↑ Donnelly, Isaak, 1999 .
6. ↑ 12 Yan , Chen, Chang, 1996 .
7. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , s. 99 Lause 6.6.1.
8. ↑ Golumbic, 1978 , s. seuraus 4.
9. ↑ Golumbic, 1978 , s. lause 2.
10. ↑ Wolk 1962 osoitti tämän juurtuneiden metsien vertailukaavioissa.
11. ↑ Wolk (1962) .
12. ↑ Brandstädt, Le, Spinrad, 1999 , s. 51.
13. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , s. 248.
14. ↑ 1 2 3 Yan, Chen, Chang, 1996 , s. lause 3.
15. ↑ Gurski, 2006 .
16. ↑ Rotem, 1981 .
17. ↑ 1 2 3 Rubio-Montiel (2015) .
18. ↑ Brandstädt, Le, Spinrad, 1999 , s. 100 Lause 6.6.3.
19. ↑ Golumbic, 1978 , s. seuraus 5.
20. ↑ Chu, 2008 .
21. ↑ Sharan (2002) .
22. ↑ Cai (1996) .
23. ↑ Nastos, Gao, 2010 .

Kirjallisuus

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Kaavioluokat: Kysely. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 0-89871-432-X .
• Cai L. Perinnöllisten ominaisuuksien kuvaajan muokkausongelmien kiinteiden parametrien ohjattavuus // Information Processing Letters . - 1996. - T. 58 , no. 4 . - S. 171-176 . - doi : 10.1016/0020-0190(96)00050-6 .
• Frank Pok Man Chu. Yksinkertainen lineaarinen aikasertifioiva LBFS-pohjainen algoritmi triviaalisti täydellisten graafien ja niiden komplementtien tunnistamiseen // Information Processing Letters . - 2008. - T. 107 , no. 1 . - s. 7-12 . - doi : 10.1016/j.ipl.2007.12.009 .
• Sam Donnelly, Garth Isaak. Hamiltonin potenssit kynnys- ja arboresoivassa vertailukäyrissä // Diskreetti matematiikka . - 1999. - T. 202 , no. 1-3 . — s. 33–44 . - doi : 10.1016/S0012-365X(98)00346-X .
• Martin Charles Golumbic. Triviaalisen täydelliset kaaviot // Diskreetti matematiikka . - 1978. - T. 24 , no. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
• Frank Gurski. Rajoitetun NLC-leveyden tai klikinleveyden operaatioiden määrittämien yhteisgraafien karakterisoinnit // Diskreetti matematiikka . - 2006. - T. 306 , no. 2 . — S. 271–277 . - doi : 10.1016/j.disc.2005.11.014 .
• James Nastos, Yong Gao. Uusi haarautumisstrategia parametroitujen graafien muokkausongelmiin // Tietojenkäsittelytieteen luentomuistiinpanot. - 2010. - T. 6509 . — S. 332–346 .
• Rotem D. Pinoa lajiteltavat permutaatiot // Discrete Mathematics . - 1981. - T. 33 , no. 2 . — S. 185–196 . - doi : 10.1016/0012-365X(81)90165-5 .
• Rubio-Montiel C. Uusi luonnehdinta triviaalisti täydellisille kuvaajille // Electronic Journal of Graph Theory and Applications. - 2015. - Osa 3 , no. 1 . — S. 22–26 . - doi : 10.5614/ejgta.2015.3.1.3 .
• Roded Sharan. Graafisen modifikaatioongelmat ja niiden sovellukset genomitutkimukseen // PhD Thesis, Tel Avivin yliopisto. – 2002.
• Wolk ES Puun vertailukaavio // Proceedings of the American Mathematical Society . - 1962. - T. 13 , no. 5 . — S. 789–795 . - doi : 10.1090/S0002-9939-1962-0172273-0 .
• Wolk ES Huomautus puun vertailukaaviosta // Proceedings of the American Mathematical Society . - 1965. - T. 16 . - S. 17-20 . - doi : 10.1090/S0002-9939-1965-0172274-5 .
• Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Kvasikynnyskaaviot // Diskreetti sovellettu matematiikka . - 1996. - T. 69 , no. 3 . — S. 247–255 . - doi : 10.1016/0166-218X(96)00094-7 .

Linkit

• Triviaalisen täydelliset kaaviot , tietojärjestelmä graafiluokista ja niiden sisällyttämisestä , < http://www.graphclasses.org/classes/gc_327.html >