Vahva olettamus täydellisistä kaavioista

Vahva täydellisen graafin arvelu  on täydellisten graafien pylväsgraafinen luonnehdinta täsmälleen sellaisina kaavioina, joissa ei ole parittomia reikiä ( parittoman pituisia generoituja jaksoja ) eikä parittomia antireikiä (parittomien reikien komplementteja). Oletuksen teki Berge vuonna 1961. Maria Chudnovskaya , Neil Robertson , Paul Seymour ja Robin Thomas esittivät todisteet vuonna 2002 [1] [2] ja julkaisivat ne vuonna 2006.

Vahvan täydellisen graafin lauseen todistamisesta kirjoittajat saivat 10 000 dollarin palkinnon Gerard Cornijolsilta Carnegie Mellonin yliopistosta [1] ja vuoden 2009 Fulkerson-palkinnon [3] .

Lauseen lause

Täydellinen kaavio  on kaavio, jossa mille tahansa luodulle aligraafille suurimman klikkin koko on yhtä suuri kuin pienin määrä värejä, jotka tarvitaan graafin värittämiseen . Täydelliset graafit sisältävät hyvin tunnetut graafiluokat, kuten kaksiosaiset kaaviot , sointukuvaajat ja vertailukelpoisuuskaaviot . Vuonna 1961 ja 1963 määritellessään näitä graafiluokkia ensimmäistä kertaa Berge totesi, että täydelliset graafit eivät voi sisältää paritonta reikää, generoitu aligraafi syklin muodossa, jonka pituus on pariton viisi tai enemmän, koska parittomat reiät ovat klikki numero kaksi ja kromaattinen numero kolme. Samoin hän huomasi, että täydelliset graafit eivät voi sisältää parittomia antireikiä, generoi aligraafia, joka täydentää parittomat aukot – parittomalla antireiällä, jossa on kärkipisteet, on klikkiluku k ja kromaattinen luku , mikä taas on mahdotonta täydellisille graafiille. Graafit, joissa ei ollut parittomia reikiä tai parittomat vastareikää, tunnettiin Berge-graafina.

Berge arveli, että mikä tahansa Berge-graafi on täydellinen, tai vastaavasti, että täydelliset graafit ja Berge-graafit määrittelevät saman graafisen luokan. Tämä olettamus tunnettiin vahvana täydellisenä graafisena arvauksena, kunnes se todistettiin vuonna 2002, jolloin se nimettiin uudelleen vahvan täydellisen graafin lauseeksi.

Yhteys heikon täydellisen graafin lauseeseen

Toinen Bergen arvelu, jonka Laszlo Lovas todisti vuonna 1972 , sanoo, että minkä tahansa täydellisen graafin komplementti on myös täydellinen. Lause tuli tunnetuksi täydellisen graafin lauseena tai (erottaakseen sen vahvasta oletuksesta/täydellisen graafin lauseesta) heikon täydellisen graafin lauseena. Koska kiellettyjen Bergen graafien karakterisointi on itseduaalista, seuraa heikko täydellisen graafin lause välittömästi vahvan täydellisen graafin lauseesta.

Ideoita todisteeksi

Chudnovskayan et al.:n todistus vahvasta täydellisen graafin lauseesta noudattaa Confortin, Cornijolsin, Robertsonin, Seymourin ja Thomasin vuonna 2001 ehdottamaa linjausta. Tämän ääriviivan mukaan mikä tahansa Berge-graafi joko muodostaa yhden viidestä peruslohkotyypistä (täydellisten graafien erityisluokat) tai sillä on yksi neljästä muusta rakenteellisesta hajotelmasta yksinkertaisempiin graafisiin. Minimaalisella epätäydellisellä Berge-graafilla ei voi olla mitään näistä hajotuksista, mikä tarkoittaa, että vastaesimerkkiä lauseelle ei voi olla olemassa [4] . Tämä ajatus perustui samantyyppiseen rakenteelliseen hajoamiseen, josta seuraisi vahva olettamus täydellisistä graafista, mutta olettamus ei osoittautunut oikeaksi [5] [6] [7] [8] .

Täydellisten graafien viisi pääluokkaa, jotka muodostavat tämän rakenteellisen hajonnan päätapaukset, ovat kaksiosaiset graafit , kaksiosaisten graafien viivakaaviot , kaksiosaisten graafien komplementit , kaksiosaisten graafien viivakaavioiden komplementit ja kaksoisjaetut graafit. On helppo nähdä, että kaksiosaiset graafit ovat täydellisiä - missä tahansa ei-triviaalissa generoidussa aligraafissa sekä klikkiluku että kromaattinen luku ovat yhtä kuin kaksi. Kaksiosaisten graafien komplementtien ja kaksiosaisten graafien viivagraafien komplementtien täydellisyys vastaa Königin lausetta , joka koskee kaksiosaisten graafien suurimpien yhteensopivuuksien kokoa , suurimpia riippumattomia joukkoja ja suurimpia pistepeitteitä. Kaksiosaisten graafien viivakaavioiden täydellisyys voidaan formuloida samalla tavalla kuin se tosiasia, että kaksiosaisten graafien kromaattinen indeksi on yhtä suuri kuin niiden suurin teho , kuten König on osoittanut [9] . Näin ollen kaikki nämä neljä perusluokkaa ovat täydellisiä. Kaksoisjaetut graafit liittyvät split -kaavioihin siinä mielessä, että ne voidaan myös osoittaa täydellisiksi [10] .

Tässä todistuksessa käsitellyt neljä hajoamistyyppiä ovat 2-liitokset, 2-liitos-komplementit, tasapainotetut vino-osiot ja homogeeniset parit.

2-liitos on graafin kärkien osio kahdeksi osajoukoksi, jolla on ominaisuus, että reunat, jotka supistavat näiden kahden osajoukon välistä leikkausta, muodostavat kahden huippupisteen ei-leikkauksen (pisteissä) täydellisiä kaksiosaisia ​​graafia . Kun graafissa on 2-liitos, se voidaan jakaa generoiduiksi aligraafiksi, joita kutsutaan "lohkoiksi" korvaamalla toinen kahdesta kärkien osajoukosta lyhimmällä polulla tämän osajoukon sisällä, joka yhdistää toisen kahdesta täydellisestä kaksiosaisesta graafista toiseen. Jos tällaista polkua ei ole, lohko muodostetaan sen sijaan korvaamalla yksi kärjen osajoukoista kahdella pisteellä, yksi jokaiselle täydelliselle kaksiosaiselle osagraafille. 2-liitos on täydellinen, jos ja vain jos sen molemmat lohkot ovat täydellisiä. Siten, jos minimaalisella epätäydellisellä graafilla on 2-liitos, sen on oltava yhtä suuri kuin jokin sen lohkoista, mikä tarkoittaa, että sen on oltava pariton sykli eikä Berge-graafi. Samasta syystä minimaalinen epätäydellinen graafi, jonka komplementissa on 2-liitos, ei voi olla Bergen graafi [11] [12] .

Vino-osio  on graafin kärkien osio kahdeksi osajoukoksi, joista toinen muodostaa irrallisen aligraafin ja toisella on irrotettu komplementti. Chvatal [13] arveli, että millään minimaalisella vastaesimerkillä vahvalle täydelliselle graafioletukselle ei voi olla vino osio. Chudnovskaya ym. esittelivät joitain teknisiä rajoituksia vinoihin osioihin ja pystyivät osoittamaan, että Chvatalin olettamus pitää paikkansa tuloksena oleville "tasapainotetuille vinostiosioille". Täydellinen olettamus on seurausta vahvasta täydellisen graafin lauseesta [14] [15] [16] .

Homogeeniset parit liittyvät graafin modulaariseen hajotukseen . Tämä on graafin hajoaminen kolmeen osajoukkoon siten, että ja yhdessä sisältävät vähintään kolme kärkeä, sisältää vähintään kaksi pistettä, ja jokaiselle pisteelle v alkaen ja mille tahansa i :lle {1,2}:sta jompikumpi v on kaikkien kärkien vieressä tai ei kumpaakaan. Minimaalisella epätäydellisellä graafilla on mahdotonta olla homogeeninen pari [17] [18] . Todistettuaan vahvan täydellisen graafisen oletuksen, Chudnovskaya [19] yksinkertaisti todistetta osoittamalla, että homogeeniset parit voidaan sulkea pois todistuksessa käytetystä hajottelujoukosta.

Todiste siitä, että mikä tahansa Berge-graafi kuuluu johonkin viidestä luokasta tai jolla on yksi neljästä hajoamistyypistä, seuraa yksittäisten tapausten analyysiä, jonka mukaan kaaviossa on tietty konfiguraatio - "venytys", aligraafi, joka voi hajotetaan kolmeen generoituun polkuun tiettyjen lisärajoitusten, laajennuslaajennus ja "oma pyörä" mukaisesti, konfiguraatio, joka liittyy pyörään , joka koostuu generoidusta syklistä, jonka keskipiste on vähintään kolmen vanteen kärjen vieressä ja joka täyttää joitain lisärajoituksia. Riippuen siitä, onko tietyssä Berge-graafissa venytys, venytyskomplementti tai oikea pyörä, voidaan osoittaa, että graafi kuuluu johonkin perusluokista, tai se voidaan hajottaa [20] [21] . Tämä tapaustutkimus täydentää todisteen.

Muistiinpanot

  1. ↑ 12 Mackenzie , 2002 .
  2. ↑ Cornuejols, 2002 .
  3. ↑ 2009 Fulkerson-palkinnot, 2011 , s. 1475-1476
  4. ↑ Cornuejols, 2002 , s. Oletus 5.1.
  5. ↑ Reed, 1986 .
  6. ↑ Hougardy, 1991 .
  7. ↑ Rusu, 1997 .
  8. ↑ Roussel, Rusu, Thuillier, 2009 , s. kohta 4.6 Ensimmäiset olettamukset.
  9. ↑ Kőnig, 1916 .
  10. ↑ Roussel, Rusu, Thuillier, 2009 , s. Määritelmä 4.39.
  11. ↑ Cornuejols, Cunningham, 1985 .
  12. ↑ Cornuejols, 2002 , s. Lause 3.2 ja johtopäätös 3.3.
  13. ↑ Chvatal, 1985 .
  14. ↑ Seymour, 2006 .
  15. ↑ Roussel, Rusu, Thuillier, 2009 , s. osa 4.7 Vino-osio.
  16. ↑ Cornuejols, 2002 , s. Lauseet 4.1 ja 4.2.
  17. ↑ Chvatal, Sbihi, 1987 .
  18. ↑ Cornuejols, 2002 , s. Lause 4.10.
  19. ↑ Chudnovsky, 2006 .
  20. ↑ Cornuejols, 2002 , s. Lauseet 5.4, 5.5, 5.6.
  21. ↑ Roussel, Rusu, Thuillier, 2009 , s. Lause 4.42.

Kirjallisuus

Linkit