Graafiteoriassa täydellinen graafi on graafi , jossa minkä tahansa generoidun aligraafin kromaattinen luku on yhtä suuri kuin tämän aligraafin maksimiklikin koko . Tiukan täydellisen graafin lauseen ansiosta on tiedetty vuodesta 2002 lähtien , että täydelliset graafit ovat samoja kuin Bergen graafit . Graafi G on Bergen graafi, jos G tai sen komplementti eivät ole generoineet parittoman pituisia syklejä (vähintään 5 reunaa).
Täydelliset kaaviot sisältävät monia tärkeitä kaavioperheitä ja tarjoavat yhtenäistyksen näiden perheiden väritykseen ja klikkeihin liittyvistä tuloksista. Esimerkiksi kaikissa täydellisissä kaavioissa väritystehtävä , maksimiklikkitehtävä ja suurin riippumaton joukko -tehtävä voidaan ratkaista polynomiajassa . Lisäksi eräät tärkeät kombinatoriikan minimax-lauseet, kuten Dilworthin lause , voidaan ilmaista täydellisinä kuvaajina ja joihinkin niihin liittyviin graafeihin.
Täydellisten graafien teoriaa on kehitetty Tibor Galai vuoden 1958 työstä lähtien , mikä nykykielellä voidaan tulkita väittämäksi, että kaksiosaisen graafin komplementti on täydellinen graafi. Tämä tulos voidaan nähdä yksinkertaisena vastineena Königin lauseelle , joka on paljon aikaisempi tulos kaksiosaisten graafien sovituksista ja vertex-peitoista. Termiä " täydellinen kaavio " käytettiin ensimmäisen kerran vuonna 1963 Claudy Bergen artikkelissa , josta nimi "Bergen graafit" tulee. Tässä artikkelissa hän yhdisti Galain tuloksen joihinkin samankaltaisiin tuloksiin määrittelemällä täydelliset graafit ja olettanut, että täydelliset graafit ja Berge-graafit ovat vastaavia. Oletus todistettiin vuonna 2002 vahvaksi täydellisen graafin lauseeksi .
Jotkut tunnetuista täydellisistä kaavioista ovat:
Kaikissa kaavioissa klikkiluku antaa kromaattisen luvun minimirajan, koska klikissä kaikki kärjet täytyy värjätä eri väreillä. Täydelliset graafit ovat niitä, joiden alaraja ei ole tarkka koko graafille vaan myös kaikille sen luomille alagraafille. Kaavioissa, jotka eivät ole täydellisiä, kromaattinen luku ja klikkausluku voivat vaihdella. Joten esimerkiksi syklille, jonka pituus on 5, tarvitaan 3 maalia, ja maksimiklikin koko on 2.
Todiste siitä, että kuvaaja on täydellinen, voidaan nähdä minimax-lauseena - näiden kaavioiden värittämiseen vaadittava värien vähimmäismäärä on yhtä suuri kuin maksimiklikin koko. Näillä termeillä voidaan ilmaista monia kombinatoriikassa tärkeitä minimax-lauseita. Esimerkiksi Dilworthin lause sanoo, että ketjujen vähimmäismäärä jaettaessa osittain järjestettyä joukkoa ketjuihin on yhtä suuri kuin antiketjujen maksimikoko , ja se voidaan muotoilla uudelleen niin, että vertailtavien graafien komplementit ovat täydellisiä. Mirskyn lause väittää, että antijonojen vähimmäismäärä antistringeiksi jaettuna on yhtä suuri kuin ketjujen maksimikoko ja vastaa samalla tavalla vertailtavien graafien täydellisyyttä.
Permutaatiograafien täydellisyys vastaa sanomista, että missä tahansa järjestetyn elementin sekvenssissä suurimman pienenevän osajonon pituus on yhtä suuri kuin sekvenssien vähimmäismäärä, kun se jaetaan kasvaviin osasarjoihin. Erdős-Szekeres-lause on helposti pääteltävissä tästä väitteestä.
Königin graafiteorian lause sanoo, että kaksiosaisen graafin minimipisteen peitto vastaa maksimisovitusta ja päinvastoin. Se voidaan tulkita kaksiosaisten graafien komplementtien täydellisyydeksi. Toinen kaksiosaisten graafien lause, jonka mukaan kromaattinen indeksi on yhtä suuri kuin graafin maksimiaste, vastaa kaksiosaisten graafien viivakaavion täydellisyyttä.
Ensimmäisessä täydellisiä graafisia käsittelevässä työssään Berge teki kaksi tärkeää olettamusta niiden rakenteesta, ja ne todistettiin myöhemmin.
Ensimmäinen näistä teoreemoista oli Laszlo Lovasin täydellisen graafin lause (1972), jonka mukaan graafi on täydellinen, jos ja vain jos sen komplementti on täydellinen. Siten täydellisyys (määritelty maksimiklikin koon ja kromaattisen luvun yhtäläisyydeksi missä tahansa generoidussa aligraafissa) vastaa riippumattoman joukon maksimikokoa ja klikkin peiton lukumäärää.
Toinen lause, jonka Berge esitti olettamuksena, tarjosi kiellettyjen graafien luonnehdinnan täydelliselle graafille.
Generoitua sykliä , jonka pituus on vähintään 5, kutsutaan parittoman pituiseksi rei'iksi . Paritonta aukkoa täydentävää aligraafia kutsutaan parittomaksi antireikiksi . Pariton sykli, jonka pituus on suurempi kuin 3, ei voi olla täydellinen, koska sen kromaattinen luku on kolme ja sen klikkiluku on kaksi. Vastaavasti ylimääräinen pariton syklikaavio, jonka pituus on 2k + 1, ei voi olla täydellinen, koska sen kromaattinen luku on k + 1 ja sen klikkiluku on k . (Tai tämän graafin epätäydellisyys johtuu täydellisen graafin lauseesta ja parittomien syklien komplementtien epätäydellisyydestä). Koska nämä graafit eivät ole täydellisiä, jokaisen täydellisen graafin on oltava Berge- graafi, graafi ilman parittomat reikiä ja ilman parittomia vastareikiä. Berge arveli, että jokainen Berge-graafi on täydellinen. Tämän todistaa lopulta Chudnovskaya , Robertson , Semur ja Thomas (2006) tiukka täydellisen graafin lause .
Täydellisen graafin lauseella on lyhyt todistus, mutta vahvan täydellisen graafin lauseen todistus on pitkä ja teknisesti vaikea. Se perustuu Berge-graafien rakenteelliseen hajoamiseen. Samanlaisia hajottelumenetelmiä syntyi myös muiden graafiluokkien, erityisesti kynsitömien graafien, tutkimuksen tuloksena .
Kaikille täydellisille graafiille graafin väritystehtävä , maksimiklikkitehtävä ja suurin riippumaton joukko -tehtävä voidaan ratkaista polynomiajassa (Grötschel, Lovász, Schrijver, 1988) [1] . Yleistapausalgoritmi käyttää ellipsoidimenetelmää lineaariseen ohjelmointiin , mutta monista erikoistapauksista tunnetut kombinatoriset algoritmit ovat tehokkaampia.
Monien vuosien ajan kysymys Bergen graafien ja täydellisten graafien tunnistamisen laskennallisesta monimutkaisuudesta pysyi avoimena. Berge-graafien määritelmästä seuraa välittömästi, että niiden tunnistaminen on tehtävä co-NP-luokasta [2] . Lopulta vahvan täydellisen graafin lauseen todistamisen jälkeen löydettiin polynomialgoritmi.