Perfekt gráf

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben perfekt gráfnak nevezünk valamely gráfot, ha minden H feszített részgráfjának kromatikus száma és klikkszáma (a legnagyobb teljes részgráf csúcsainak száma) megegyezik:

\chi(H) = \omega(H)

A klikkszám minden gráf esetén alsó becslést ad a kromatikus számra, hiszen a színezés során a legnagyobb klikk csúcsai mind különböző színt kapnak, azaz ennyi színre biztosan szükség van a gráf kiszínezéséhez. Azok a gráfok perfektek, amelyekre ez a becslés éles, nemcsak magában a gráfban, hanem minden feszített részgráfjában is.

Nem perfekt gráfok színezéséhez több színre is szükség lehet, mint a legnagyobb klikk mérete. Ilyenek a páratlan és legalább 5 hosszúságú körök, amelyek színezéséhez legalább 3 szín kell, de a legnagyobb klikk mérete csak 2.

Történetük[szerkesztés | forrásszöveg szerkesztése]

A perfekt gráfok elmélete Gallai Tibor 1958-as eredményéből alakult ki. Gallai eredménye szerint minden páros gráf komplementere perfekt. Ez az eredmény egyenértékűnek tekinthető a Kőnig-tétellel, ami egy sokkal korábbi eredmény a párosításokkal és csúcsfedésekkel kapcsolatban páros gráfokban. A perfekt gráf kifejezés 1963-ban Claude Berge tanulmányában jelent meg először. Ebben a tanulmányban Berge definiálta a perfekt gráf fogalmát. Egyesítette Gallai eredményeit néhány hasonló eredménnyel és megfogalmazta a perfekt gráfok karakterizációjáról szóló sejtését, az erős perfekt gráf sejtést. 1972-ben Lovász Lászlónak sikerült bebizonyítania, hogy egy gráf akkor és csak akkor perfekt, ha komplementere perfekt.

Perfekt gráfok[szerkesztés | forrásszöveg szerkesztése]

Egy G gráf perfekt, ha \chi(G) = \omega(G) (G gráf kromatikus száma megegyezik G klikkszámával) és ez G minden feszített részgráfjára is teljesül.

Feszített részgráf: kiválasztjuk egy gráf néhány csúcsát és minden olyan élét amely a kiválasztott csúcsok között fut, ekkor a kiválasztott pontokból és élekből álló gráf az eredeti gráf feszített részgráfja.

Példák perfekt gráfokra[szerkesztés | forrásszöveg szerkesztése]

Egy gráf merevkörű, ha minden 3-nál hosszabb körnek van húrja (azaz nincs feszített, 3-nál hosszabb kör)

Speciális perfekt gráfok[szerkesztés | forrásszöveg szerkesztése]

Intervallumgráf[szerkesztés | forrásszöveg szerkesztése]

Definíció: A gráfelméletben az intervallumgráf olyan gráf, aminek a pontjai megfeleltethetőek a valós számok egy-egy intervallumának, és két pontja között pontosan akkor van él, ha a megfelelő intervallumok metszete nem üres.

Tétel: Minden intervallumgráf perfekt.

Bizonyítás: Intervallumgráfoknak feszített részgráfjai is intervallumgráfok, tehát elég belátni, hogy minden intervallumgráfra \chi(G)=\omega(G). Azt tudjuk, hogy \chi(G)\geq\omega(G) ezért elég belátni, hogy \omega(G)\geq\chi(G). Legyen \omega(G)=k. Színezzük az intervallumokat bal végpontjuk szerint, balról jobbra, a legelső színnel, ami nem mond ellent a korábbi intervallumok színezésének (ez tehát a mohó algoritmus használata). Ha a k+1-edik színt kellene használnunk valamelyik intervallum színezéséhez, az azt jelentené, hogy ennek az intervallumnak q bal oldali végpontja benne van k másik intervallumban. Ez azt jelentené, hogy van a gráfban k+1 méretű klikk, ami ellentmondás. (Hiszen \omega(G)=k, azaz a legnagyobb klikk mérete k).

Páros gráfokkal kapcsolatos tételek[szerkesztés | forrásszöveg szerkesztése]

Tétel: Minden páros gráf perfekt.

Bizonyítás: Páros gráf minden feszített részgráfja szintén páros gráf. Ezért elég belátni, hogy minden G páros gráfra \chi(G) = \omega(G) ,ami igaz, mert egy páros gráf 2 színnel színezhető és nem tartalmaz háromszöget, tehát klikkszáma is 2.

Tétel: Minden G páros gráf  \overline{G}  komplementere perfekt.

Bizonyítás: Páros gráf komplementerének feszített részgráfja egy páros gráf komplementere. (Az eredeti páros gráf megfelelő feszített részgráfjának komplementere.) Elég belátni, hogy   \chi(\overline{G}) = \omega(\overline{G}).  Mivel  \chi(\overline{G}) \geq \omega(\overline{G})  minden gráfra teljesül, azt kell belátni, hogy   \overline{G}  kiszínezhető   \omega(\overline{G})  színnel.

Legyen X ∪ Y egy maximális méretű klikk  \overline{G}  -ben, X ⊆ A és Y ⊆ B. Ekkor X ∪ Y a G gráfban egy független ponthalmazt alkot.

Perfekt gráf-bizonyítás.jpg      Perfekt gráf-bizonyítás2.jpg

Van G-ben olyan párosítás, ami A \ X minden pontjához egy Y -beli pontot párosít. Ha nincs, akkor a Hall-tétel szerint létezik egy olyan ZA \ X ponthalmaz az (A \ X) ∪ Y által feszített páros gráfban, amelyre |N(Z)| < |Z|. Ekkor (XZ) ∪ (Y \ N(Z)) egy XY -nál nagyobb klikk  \overline{G}  -ben (üres G -ben).

Hasonlóan, G -ben van párosítás, ami B \ Y -t X -be párosítja. Ezáltal  \overline{G}  -ben minden (A \ X) ∪ (B \ Y) -beli ponthoz rendeltünk egy vele nem szomszédos XY -beli pontot.

XY pontjait kiszínezzük \omega(G) színnel, minden további pontot kiszínezhetünk úgy, hogy az előbb definiált párjának színét adjuk neki. Ez jó színezés, hiszen minden szín legfeljebb két ponton fordul elő, és ezek biztosan nem szomszédos pontok.

Perfekt gráf tételek[szerkesztés | forrásszöveg szerkesztése]

Perfekt gráf tétel [1][szerkesztés | forrásszöveg szerkesztése]

Tétel: Egy gráf akkor és csak akkor perfekt, ha a komplementere perfekt.

Eredetileg ez volt a (gyenge) perfektgráf-sejtés (Fulkerson, 1971). Lovász László látta be 1972-ben.

Később Lovász igazolta, hogy egy G gráf pontosan akkor perfekt, ha minden H feszített részgráfjára igaz

\omega(H)\omega(\overline{H})\geq |V(H)|.

Mivel ez a feltétel szimmetrikus G-re és G komplementerére, az eredmény azonnal adja a perfekt gráf tételt.

Erős perfekt gráf tétel [2][szerkesztés | forrásszöveg szerkesztése]

Mely gráfok nem perfektek? Nem perfekt egy legalább öt hosszú páratlan kör, hiszen ebben a maximális klikk mérete 2, viszont kromatikus száma 3. Az előbbi tétel szerint a legalább öt hosszú páratlan körök komplementerei sem perfektek. Ennek megfordítása több évtizedig nyitott volt.

Tétel: Egy G gráf akkor és csak akkor perfekt, ha sem G, sem  \overline{G}  nem tartalmaz feszített részgráfként legalább öt hosszú páratlan kört.

Ezt már Berge megsejtette 1960-61-ben, akkor erős perfektgráf-sejtés néven lett ismert.

Nem sokkal ezután Chudnovsky, Cornuéjols, Liu, Seymour és Vušković polinomiális algoritmust talált annak eldöntésére, hogy egy adott gráf perfekt-e.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. (Lovász 1972). (Hozzáférés: 2009. május 13.)
  2. (Chudnovsky, Robertson, Seymour, Thomas 2002). (Hozzáférés: 2009. május 13.)
  • Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó. ISBN 963-9326-68-2 (2001) 
  • Friedl Katalin, Recski András, Simonyi Gábor. Gráfelméleti feladatok. Typotex Kiadó. ISBN 963-9664-01-4 (2006) 
  • Perfect Graph
  • Dr. Takách Géza előadása
  • The Strong Perfect Graph Theorem (Vašek Chvátal).
  • Nyitott problémák perfekt gráfokkal (American Institute of Mathematics).
  • Perfect graph (Wolfram Mathworld).
  • L. Lovász: Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 2 (1972), 253–267.
  • Lovász László: A kombinatorika minimax tételeiről, Matematikai Lapok, 26 (1976), 209–264.
  • M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas: The strong perfect graph theorem, Annals of Mathematics, 164 (2006), 51–229.
  • M. Chudnovsky, G. Cornuéjols, X. Liudagger, P. Seymour, K. Vuskovic: Recognizing Berge Graphs, Combinatorica, 25 (2005), 143–186.

Javasolt könyvek, cikkek, linkek[szerkesztés | forrásszöveg szerkesztése]

Könyvek[szerkesztés | forrásszöveg szerkesztése]

  • László, Lovász. Combinatorical Problems and Exercises. Akadémiai Kiadó (1979) 
  • Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó. ISBN 963-9326-68-2 (2001) 

Cikkek[szerkesztés | forrásszöveg szerkesztése]

  • Berge, Claude (1963). „Perfect graphs”. Six Papers on Graph Theory: 1–21, Calcutta: Indian Statistical Institute. 
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006.). „The strong perfect graph theorem”. Annals of Mathematics 164 (1), 51–229. o.  
  • Gallai, Tibor (1958.). „Maximum-minimum Sätze über Graphen”. Acta Math. Acad. Sci. Hungar. 9, 395–434. o. DOI:10.1007/BF02020271.  
  • Lovász, László (1972.). „Normal hypergraphs and the perfect graph conjecture”. Discrete Mathematics (journal) 2, 253–267. o. DOI:10.1016/0012-365X(72)90006-4.  

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]