Páros gráf

A páros gráf
Definíció
Olyan gráf, amelyben csúcsok két részre bonthatóak úgy, hogy az egyes csoportokon belül nincsenek élek.

egy páros gráfban minden kör (ha van) páros hosszúságú, azaz
páros gráfban nincs páratlan hosszúságú kör, ...

Párosítások páros gráfokban
Tétel (Kőnig tétele): Páros gráfokban v(G)=T(G).
Bizonyítás: Több bizonyítási módszer is adható. Ezeket itt nem részletezzük, de némelyikhez pointert adunk, némelyek kidolgozását a hallgatóra bízzuk.

páros gráf
Olyan gráf, melynek a pontjai a és diszjunkt halmazba oszthatók úgy, hogy pontjai közül semelyik kettő között nem halad él, és ugyanígy pontjai között sem.

Ha egy páros gráf, akkor -ben akkor és csak akkor van -et lefedő párosítás, ha minden részhalmazra.
A Hall-tételnek főleg a gráfelméleten belül vannak alkalmazásai. Gráfelméleti problémaként így fogalmazhatjuk meg az alapkérdést: ...

Úgynevezett páros gráffal van dolgunk, mert pontjai két olyan csoportra oszthatók (tudniillik fiúkra és lányokra), melyeken belül nincs él (kapcsolat), tehát él csak különböző halmazba tartozó pontokat köthet össze.

See also: Gráf, Él, Bizonyítás, Halmaz, Végpont