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 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: .
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 -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 összefüggő 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.
Következmény
[szerkesztés]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
[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