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 G gráfot, ha G csúcsainak halmazát fel tudjuk úgy osztani egy A és B halmazra, hogy az összes G-beli élre teljesül, hogy az egyik végpontja A-ban van, a másik pedig B-ben. Egy G páros gráfot következőképpen jelölünk: G = (A,B).

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 A-beli pont össze van kötve minden B-beli ponttal. Jelölés: K_{a,b}, ahol a = |A| és b = |B|.

Szükséges és elégséges feltétel[szerkesztés | forrásszöveg szerkesztése]

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

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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

A másik irányhoz megmutatjuk, hogy ha G minden köre páros sok pontból áll, akkor meg tudunk adni megfelelő A és B halmazokat. Tekintsünk egy tetszőleges x pontot a gráfban. Ezt rakjuk A-ba. Most, x minden szomszédját rakjuk B-be, és az összes olyan B-beli pont szomszédját amelyet még nem helyeztünk el, rakjuk A-ba. Ezt folytassuk amíg minden pontot el nem helyeztünk A-ba vagy B-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 | forrásszöveg szerkesztése]

Minden páros gráf perfekt.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Egy G 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 \omega(G) = \chi(G). Ez triviálisan igaz, ugyanis egy páros gráf háromszögmentes, \omega(G) = \chi(G)s ha legalább egy éle van akkor \omega(G) = 2 és \chi(G) = 2. Ha nincs éle a gráfnak, akkor pedig \omega(G) = \chi(G) = 1.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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