Páros gráfnak, kétrészes gráfnak vagy páros körüljárású gráfnak nevezünk egy gráfot, ha csúcsainak halmazát fel tudjuk úgy osztani egy és halmazra, hogy az összes -beli élre teljesül, hogy az egyik végpontja -ban van, a másik pedig -ben. Egy páros gráfot következőképpen jelölünk: .

Példa egy páros gráfra

Páros gráf minden részgráfja is páros. Minden fa páros gráf.

Teljes páros gráfnak nevezünk egy olyan páros gráfot melyben minden -beli pont össze van kötve minden -beli ponttal. Jelölés: , ahol és .

Szükséges és elégséges feltételSzerkesztés

Egy   gráf akkor és csak akkor páros, ha minden  -beli kör páros hosszúságú.

BizonyításSzerkesztés

Az első irány nyilvánvaló, ugyanis ha   egy kör a   páros gráfban, akkor   pontjai alternálnak   és   között. Tehát világos hogy  -nek páros sok csúcsa van.

A másik irányhoz megmutatjuk, hogy ha   minden köre páros sok pontból áll, akkor meg tudunk adni megfelelő   és   halmazokat. Tekintsünk egy tetszőleges   pontot a gráfban. Ezt rakjuk  -ba. Most,   minden szomszédját rakjuk  -be, és az összes olyan  -beli pont szomszédját, amelyet még nem helyeztünk el, rakjuk  -ba. Ezt folytassuk, amíg minden pontot el nem helyeztünk  -ba vagy  -be. Ez az algoritmus azért lesz jó, mert ha egy halmazban lenne két szomszédos csúcs, akkor a gráfban lenne páratlan kör is, ez viszont ellentmondás.

2. TételSzerkesztés

Minden páros gráf perfekt.

BizonyításSzerkesztés

Egy   páros gráfnak minden feszített részgráfja is páros gráf, ezért elég belátni, hogy minden páros gráfra      . Ez triviálisan igaz, ugyanis egy páros gráf háromszögmentes,      s ha legalább egy éle van akkor       és      . Ha nincs éle a gráfnak, akkor pedig          .

Kapcsolódó szócikkekSzerkesztés

HivatkozásokSzerkesztés

  • Katona Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai. Typotex Kiadó, 2006. ISBN 963-9664-19-7