Páros gráf

A Wikipédiából, a szabad enciklopédiából
Példa egy páros gráfra

Páros 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á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étel[szerkesztés]

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

Bizonyítás[szerkeszté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étel[szerkesztés]

Minden páros gráf perfekt.

Bizonyítás[szerkeszté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 .

Lásd még[szerkesztés]

Hivatkozások[szerkesztés]

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