Perfekt gráf

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

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 perfektgrá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

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

fagráfok
teljes gráfok
páros gráfok, komplementereik (Kőnig Dénes) és élgráfjaik
intervallumgráfok
páros gráfok élgráfjai
összehasonlítási gráfok
merevkörű gráfok (minden 3-nál hosszabb körnek van húrja, tehát nincs feszített, 3-nál hosszabb kör)

Speciális perfekt gráfok

Intervallumgráf

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

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.

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 Z ⊆ A \ X ponthalmaz az (A \ X) ∪ Y által feszített páros gráfban, amelyre |N(Z)| < |Z|. Ekkor (X ∪ Z) ∪ (Y \ N(Z)) egy X ∪ Y -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 X ∪ Y-beli pontot.

X ∪ Y 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.

Perfektgráf-tételek

Perfektgráf-tétel

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

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 perfektgráf-tételt.

Erős perfektgráf-tétel

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. ^[2] 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.

Jegyzetek

↑ (Lovász 1972). (Hozzáférés: 2009. május 13.)^{[halott link]}
↑ (Chudnovsky, Robertson, Seymour, Thomas 2002). (Hozzáférés: 2009. május 13.)

Források

Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó (2001). ISBN 963-9326-68-2

Friedl Katalin, Recski András, Simonyi Gábor. Gráfelméleti feladatok. Typotex Kiadó (2006). ISBN 963-9664-01-4
Dr. Takách Géza előadása^{[halott link]}
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

Könyvek

Golumbic, Martin Charles. Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980). ISBN 0-444-51530-5 Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

László, Lovász. Combinatorial Problems and Exercises. Akadémiai Kiadó (1979)

Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó (2001). ISBN 963-9326-68-2

Cikkek

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.

További információk

[1] (Lovász 1972). (Hozzáférés: 2009. május 13.)^{[halott link]}

[2] (Chudnovsky, Robertson, Seymour, Thomas 2002). (Hozzáférés: 2009. május 13.)

[1]

[2]