Páros gráf

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

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

Kapcsolódó szócikkek[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