Páros gráf

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

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

Bizonyítás

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

Minden páros gráf perfekt.

Bizonyítás

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

Kapcsolódó szócikkek

• Kőnig-tétel
• Többrészes gráf
• Páros gráf fele

Hivatkozások

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