Páros gráf

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

Kézenfekvő példa a következő: legyenek a gráf csúcsai egy sakktábla mezői, két csúcs közé akkor vegyünk fel élt, ha egyik a másikról üthető huszárral. Ekkor A-ba a világos, B-be a sötét mezőket helyezve páros gráfot kapunk, hiszen bármely mezőről csak eltérő színű mező üthető.

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

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

Egy összefüggő ${\displaystyle G}$ gráf akkor és csak akkor páros, ha minden ${\displaystyle G}$-beli kör páros hosszúságú.

Bizonyítás

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

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

Következmény

Nem összefüggő gráf pontosan akkor páros, ha komponensei külön-külön párosak.

Bizonyítás: A tételt kell komponensenként alkalmazni.

2. Tétel

Minden páros gráf perfekt.

Bizonyítás

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