Perfekt gráf

matematikai fogalom a gráfelméletben
Ez a közzétett változat, ellenőrizve: 2021. március 31.

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:

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

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

szerkesztés

Egy G gráf perfekt, ha   (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

Speciális perfekt gráfok

szerkesztés

Intervallumgráf

szerkesztés

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  . Azt tudjuk, hogy   ezért elég belátni, hogy  . Legyen  . 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  -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   másik intervallumban. Ez azt jelentené, hogy van a gráfban   méretű klikk, ami ellentmondás. (Hiszen  , azaz a legnagyobb klikk mérete k).

Páros gráfokkal kapcsolatos tételek

szerkesztés

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   ,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     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    .  Mivel     minden gráfra teljesül, azt kell belátni, hogy      kiszínezhető      színnel.

Legyen X ∪ Y egy maximális méretű klikk     -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 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     -ben (üres G-ben).

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

XY pontjait kiszínezzük   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

szerkesztés

Perfektgráf-tétel

szerkesztés

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

 

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

szerkesztés

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     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.

  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.)
  • 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

szerkesztés
  • Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó (2001). ISBN 963-9326-68-2 
  • 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

szerkesztés