Täydellinen kaavio - Perfect graph

Paley kuvaaja järjestyksen 9 väritetty kolme väriä ja osoittaa klikki kolmen kärjet. Tässä kaaviossa ja jokaisessa sen indusoidussa osakaaviossa kromaattinen luku on yhtä suuri kuin klikki, joten se on täydellinen kuvaaja.

Vuonna Graafiteoria , eli täydellinen kuvaaja on kaavio , jossa kromaattinen numero jokaisen indusoi aligraafia vastaa järjestystä suurin klikki tuon aligraafia ( klikki numero ). Vastaavasti symbolisesti ilmaistuna mielivaltainen kuvaaja on täydellinen silloin ja vain, jos meillä on kaikki . ${\ displaystyle G = (V, E)}$${\ displaystyle S \ subseteq V}$${\ displaystyle \ chi (G [S]) = \ omega (G [S])}$

Täydellinen kuvaajat sisältävät monia tärkeitä perheiden kaavioita ja palvella yhtenäistää tuottamisesta väriaineita ja klikkien näissä perheissä. Esimerkiksi kaikissa täydellisissä kaavioissa kuvaajan väritysongelma , suurin klikkausongelma ja suurin riippumaton joukkoongelma voidaan ratkaista polynomiajassa . Lisäksi useita tärkeitä min-max-lauseita yhdistelmätekniikassa , kuten Dilworthin lause , voidaan ilmaista tiettyjen niihin liittyvien kaavioiden täydellisyytenä.

Kaavio on 1-täydellinen, jos ja vain jos . Tällöin se on täydellinen silloin ja vain, jos jokainen sen alakuvaaja on 1-täydellinen. ${\ displaystyle G}$${\ displaystyle \ chi (G) = \ omega (G)}$${\ displaystyle G}$${\ displaystyle G}$

Ominaisuudet

• Vuoteen täydellinen kuvaajan lauseen , kuvaaja on täydellinen, jos ja vain jos sen täydennys on täydellinen.${\ displaystyle G}$ ${\ displaystyle {\ bar {G}}}$
• Jonka vahva täydellinen kuvaaja lause , täydellinen kuvaajat ovat samat kuin Berge kaavioita, jotka ovat kuvaajia, joissa ei voida eikä sisältää indusoidun jakson parittoman pituus 5 tai enemmän.${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle {\ bar {G}}}$

Katso lisätietoja alla olevasta osiosta.

Historia

Teoria Täydellinen kuvaajia kehittynyt 1958 tuloksesta Tibor Gallai että nykyaikainen kieli voidaan tulkita toteamalla, että täydennys on kaksijakoinen verkko on täydellinen; tätä tulosta voidaan pitää myös yksinkertaisena vastineena Kőnigin lauseelle , paljon aikaisempaan tulokseen, joka liittyy täsmäytyksiin ja kärkipäällysteisiin kahdenvälisissä kuvaajaissa. Ilmaus "täydellinen kuvaaja" näkyy ensimmäistä kertaa Claude Bergen vuonna 1963 julkaisussa , jonka mukaan Bergen kuvaajat on nimetty. Tässä artikkelissa hän yhdisti Gallain tuloksen useilla vastaavilla tuloksilla määrittelemällä täydelliset kaaviot, ja hän arvasi täydellisen kuvaajan ja Bergen kuvaajan määritelmien vastaavuuden; hänen oletuksensa osoittautui vuonna 2002 vahvan täydellisen kuvaajan teoreemiksi .

Täydellisten kaavioiden perheet

Jotkut tunnetuimmista täydellisistä kaavioista ovat:

• Kaksipuoliset kuvaajat , jotka ovat kaavioita, jotka voidaan värittää kahdella värillä, mukaan lukien metsät (kaaviot ilman syklejä).
• Viivakaavioiden of kaksiosaisesta kuvaajat (katso Kőnig lause ). Rookin kaaviot (viivakaaviot täydellisistä kahdenvälisistä kaavioista ) ovat erikoistapaus.
• Chordal -kuvaajat , kuvaajat, joissa jokaisessa neljän tai useamman kärjen syklissä on sointu , reuna kahden kärkipisteen välillä, jotka eivät ole peräkkäisiä syklissä. Nämä sisältävät
  • metsät, k -puut (suurimmat kuvaajat tietyllä puuleveydellä ),
  • jaetut kuvaajat (kuvaajat, jotka voidaan jakaa osioiksi ja itsenäisiksi joukkoiksi),
  • lohkokaaviot (kaaviot, joissa jokainen kaksoiskytketty komponentti on klikki),
  • Ptolemaioksen kuvaajat (kuvaajat, joiden etäisyydet noudattavat Ptolemaioksen eriarvoisuutta ),
  • välikaaviot (kuvaajat, joissa jokainen kärki edustaa suoran väliä ja jokainen reuna edustaa kahden välin välistä tyhjää leikkausta),
  • triviaalisesti täydelliset kuvaajat (intervallikaaviot sisäkkäisille aikaväleille), kynnyskaaviot (kaaviot, joissa kaksi kärkeä ovat vierekkäin, kun niiden kokonaispaino ylittää numeerisen kynnyksen),
  • tuulimyllykaaviot (muodostettu yhdistämällä samanlaiset klikit yhteiseen pisteeseen),
  • ja voimakkaasti sointukäyrät (sointukaaviot, joissa jokaisella parillisella jaksolla, jonka pituus on kuusi tai enemmän, on pariton sointu).
• Vertailukelpoisuuden kuvaajat, jotka on muodostettu osittain järjestetyistä joukkoista yhdistämällä elementtiparit reunalla aina kun ne liittyvät toisiinsa osittaisessa järjestyksessä. Nämä sisältävät:
  • kahdenväliset kuvaajat, intervallikaavioiden täydennykset, triviaalisesti täydelliset kaaviot, kynnyskaaviot, tuulimyllykaaviot,
  • permutaatiokäyrät (kaaviot, joissa reunat edustavat permutaatiolla käänteisiä elementtipareja),
  • ja graafit (kaaviot, jotka muodostuvat diskursiivisen liiton ja täydentämisen rekursiivisista operaatioista).
• Täysin tilattavat kaaviot , jotka ovat kaavioita, jotka voidaan tilata siten, että ahne väritysalgoritmi on optimaalinen jokaisella indusoidulla alikuvaajalla. Näitä ovat kahdenväliset kuvaajat, sointukaaviot, vertailtavuuskäyrät,
  • etäisyysperinnölliset kaaviot (joissa lyhyimmät reittietäisyydet yhdistetyissä indusoiduissa osakaavioissa ovat yhtä suuret kuin koko kaaviossa),
  • ja pyörägraafit, joissa on pariton määrä pisteitä.
• Puolisuunnikekäyrät , jotka ovat puolisuunnikkeen leikkauspiirteitä , joiden yhdensuuntaiset reunaparit sijaitsevat kahdella yhdensuuntaisella suoralla. Näitä ovat intervallikaaviot, triviaalisesti täydelliset kaaviot, kynnyskaaviot, tuulimyllykaaviot ja permutaatiokaaviot; niiden täydennykset ovat vertailukelpoisuuskaavioiden osajoukko.

Suhde min-max-lauseisiin

Kaikissa kaavioissa napsautusluku antaa alarajan kromaattiselle numerolle, koska kaikki klikin kärkipisteet on määritettävä eri väreillä missä tahansa oikeassa värissä. Täydelliset kaaviot ovat niitä, joille tämä alaraja on tiukka, ei vain kaaviossa itsessään, vaan kaikissa sen indusoimissa osakaavioissa. Kaavioissa, jotka eivät ole täydellisiä, kromaattinen luku ja klikki voivat vaihdella; Esimerkiksi viiden pituinen sykli vaatii kolme väriä missä tahansa oikeassa värissä, mutta sen suurin klikki on koko kaksi.

Todiste siitä, että kuvaajaluokka on täydellinen, voidaan nähdä min-max-lauseena: näihin kaavioihin tarvittava värin vähimmäismäärä on yhtä suuri kuin klikin maksimikoko. Monet tärkeät min-max-lauseet kombinatorikassa voidaan ilmaista näillä termeillä. Esimerkiksi Dilworthin lause sanoo, että ketjujen vähimmäismäärä osittain järjestetyn joukon osioissa ketjuiksi on yhtä suuri kuin ketjun enimmäiskoko , ja se voidaan muotoilla uudelleen todetuksi , että vertailukelpoisten kaavioiden täydennykset ovat täydellisiä. Mirskyn lause sanoo, että antichaine -osioiden vähimmäismäärä osioksi antichaineiksi on yhtä suuri kuin ketjun maksimikoko ja vastaa samalla tavalla vertailukelpoisten kaavioiden täydellisyyttä.

Permutaatiokäyrien täydellisyys vastaa väitettä, että jokaisessa järjestettyjen elementtien sekvenssissä pisimmän pienenevän alisekvenssin pituus on yhtä suuri kuin jaksojen vähimmäismäärä osiossa kasvaviin alisekvensseihin. Erdős-Szekeres teoreema on helppo seuraus tätä väitettä.

Kőnigin lause graafiteoriassa toteaa, että kaksipuoleisen kuvaajan minimipistepeite vastaa enimmäissovitusta ja päinvastoin; sitä voidaan tulkita kahden osapuolten kuvaajan täydentävyydeksi. Toinen lause, joka koskee kaksipuolisia kuvaajaa, että niiden kromaattinen indeksi vastaa niiden enimmäisastetta , vastaa kaksipuolisten kuvaajan viivakaavioiden täydellisyyttä.

Karakterisaatiot ja täydelliset kuvaajalauseet

Alkuperäisessä työssä täydellisten kaavioiden suhteen Berge teki kaksi tärkeää olettamusta niiden rakenteesta, jotka todistettiin vasta myöhemmin.

Ensimmäinen näistä kahdesta lauseesta oli Lovászin (1972) täydellinen graafilause , jossa todettiin, että kuvaaja on täydellinen silloin ja vain, jos sen täydennys on täydellinen. Täydellisyys (joka määritellään maksimiklikin koon ja kromaattisen luvun yhtäläisyydeksi jokaisessa indusoidussa alikaaviossa) on yhtä suuri kuin riippumattoman joukon suurimman koon ja klikin kannen numeron yhtäläisyys.

Seitsemän kärjen sykli ja sen täydennys, joka näyttää joka tapauksessa optimaalisen värin ja maksimaalisen klikin (esitetty raskailla reunoilla). Koska kumpikaan kuvaaja ei käytä klikkin kokoa vastaavia värejä, kumpikaan ei ole täydellinen.

Toinen lause, jonka Berge arveli, tarjosi täydellisten kaavioiden kielletyn kuvaajan kuvauksen . Indusoi sykli parittoman pituus vähintään 5 kutsutaan pariton reikä . Indusoitua osakaaviota, joka on parittoman reiän täydennys, kutsutaan parittomaksi reikäksi . Pariton sykli, jonka pituus on suurempi kuin 3, ei voi olla täydellinen, koska sen kromaattinen luku on kolme ja sen klikkausluku on kaksi. Samoin parittoman syklin, jonka pituus on 2 k  + 1 , komplementti ei voi olla täydellinen, koska sen kromaattinen luku on k  + 1 ja sen klikkausluku on k . (Vaihtoehtoisesti tämän kuvaajan epätäydellisyys seuraa täydellisestä kuvaajan lauseesta ja täydentävän parittoman syklin epätäydellisyydestä). Koska nämä kuvaajat eivät ole täydellisiä, jokaisen täydellisen kuvaajan on oltava Bergen kuvaaja , kuvaaja, jossa ei ole parittomia reikiä eikä parittomia reikiä. Berge arveli päinvastoin, että jokainen Bergen kuvaaja on täydellinen. Tämä oli lopulta osoittautunut kuin vahva täydellinen kuvaaja lauseen ja Chudnovsky , Robertson , Seymour , ja Thomas (2006). Se merkitsee triviaalisti täydellistä kuvaajan teoreemia, joten nimi.

Täydellisen kuvaajan lauseella on lyhyt todiste, mutta vahvan täydellisen kuvaajan lauseen todiste on pitkä ja tekninen, ja se perustuu Bergen kuvaajan syvään rakenteelliseen hajoamiseen. Aiheeseen liittyvät hajoamistekniikat ovat tuottaneet hedelmää myös muiden kuvaajaluokkien tutkimuksessa ja erityisesti kynsittömien kaavioiden osalta .

On myös kolmas lause, joka johtuu jälleen Lovászista, jonka Hajnal alun perin ehdotti . Siinä todetaan, että kuvaaja on täydellinen, jos suurimman klikin ja suurimman riippumattoman joukon koot kerrottuna yhteen ovat yhtä suuret tai suuremmat kuin käyrän kärkien lukumäärä, ja sama pätee kaikkiin indusoituihin osakaavioihin. Se on helppo seuraus vahvan täydellisen kuvaajan lauseesta, kun taas täydellinen kuvaajan lause on helppo seuraus siitä.

Hajnal -luonnehdinta ei täytä parittomia n -sykliä tai niiden täydennyksiä n > 3 : parittomassa syklissä n > 3 kärjessä on klikki numero 2 ja riippumattomuusluku ( n -1)/2 . Komplementille on päinvastoin, joten molemmissa tapauksissa tuote on n - 1 .

Algoritmit täydellisissä kaavioissa

Kaikissa täydellinen kuvaajien kaavio väritys ongelma , suurin klikki ongelma , ja suurin riippumaton joukko ongelma voidaan kaikki ratkaista polynomiajassa ( Grötschel, Lovasz & Schrijver 1988 ). Yleisen tapauksen algoritmi sisältää näiden kaavioiden Lovász -luvun , joka (tietyn kaavion täydennykseksi) on asetettu kromaattisen luvun ja napsautusluvun väliin. Lasketaan Lovasz numero voidaan formuloida semidefiniitti ohjelma ja arvioida numeerisesti polynomiajassa käyttäen ellipsoidin menetelmää varten lineaarisen ohjelmoinnin . Täydellisten kaavioiden saamiseksi pyöristämällä tämä approksimaatio kokonaisluvuksi saadaan kromaattinen luku ja klikkiluku polynomiajassa; suurin riippumaton joukko voidaan löytää soveltamalla samaa lähestymistapaa kaavion täydennykseen. Tämä menetelmä on kuitenkin monimutkainen ja sillä on korkea polynomi -eksponentti. Tehokkaampia yhdistelmäalgoritmeja tunnetaan monista erityistapauksista.

Monien vuosien ajan Bergen kaavioiden ja täydellisten kaavioiden tunnistaminen oli monimutkaista. Bergen kuvaajan määritelmästä seuraa välittömästi, että niiden tunnistaminen on yhteis-NP: ssä (Lovász 1983). Lopuksi vahvan täydellisen kuvaajan lauseen todistamisen jälkeen Chudnovsky, Cornuéjols, Liu, Seymour ja Vušković löysivät polynomi -aika -algoritmin.

Viitteet

• Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe . 10 : 114.
• Berge, Claude (1963). "Täydelliset kaaviot". Kuusi julkaisua graafiteoriasta . Calcutta: Intian tilastolaitos. s. 1–21.
• Chudnovsky, Maria ; Cornuéjols, Gérard ; Liu, Xinming; Seymour, Paul ; Vušković, Kristina (2005). "Bergen kaavioiden tunnistaminen" . Yhdistelmä . 25 (2): 143–186. doi : 10.1007/s00493-005-0012-8 . S2CID  2229369 .
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006). "Vahva täydellinen kuvaajan lause" . Matematiikan vuosikirjat . 164 (1): 51–229. arXiv : matematiikka/0212070 . doi : 10.4007/annals.2006.164.51 . S2CID  119151552 .
• Gallai, Tibor (1958). "Suurin-minimi Sätze über Graphen" . Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. doi : 10.1007/BF02020271 . S2CID  123953062 .
• Golumbic, Martin Charles (1980). Algoritminen kuvaajateoria ja täydelliset kuvaajat . Academic Press. ISBN 0-444-51530-5. Arkistoitu alkuperäisestä 2010-05-22 . Haettu 21.11.2007 . Toinen painos, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1988). Geometriset algoritmit ja yhdistelmäoptimointi . Springer-Verlag. Katso erityisesti luku 9, "Stabiilit kuvaajat", s. 273–303.
• Lovász, László (1972). "Normaalit hypergrafit ja täydellinen kuvaajan olettamus" . Erillinen matematiikka . 2 (3): 253–267. doi : 10.1016/0012-365X (72) 90006-4 .
• Lovász, László (1972). "Täydellisten kaavioiden luonnehdinta" . Journal of Combinatorial Theory . B-sarjan 13 (2): 95-98. doi : 10.1016/0095-8956 (72) 90045-7 .
• Lovász, László (1983). "Täydelliset kaaviot". Julkaisussa Beineke, Lowell W .; Wilson, Robin J. (toim.). Selected Topics in Graph Theory, Vuosikerta 2 . Academic Press. s. 55–87. ISBN 0-12-086202-6.

Ulkoiset linkit

• Strong Perfect Graph Lause , jonka Václav Chvatal .
• Avoimet tehtävät täydellisissä kaavioissa , joita ylläpitää American Institute of Mathematics .
• Täydelliset ongelmat , ylläpitäjä Václav Chvátal.
• Tietojärjestelmä kaavioluokkien sisällyttämiseen : täydellinen kaavio