Van itt ez a páros gráf…

És próbáljuk meg kideríteni, hogy van-e benne A-t fedő párosítás.

Kezdjünk el kísérletezni.

Hát, majdnem.

Próbálkozhatunk újra, de úgysem fog sikerülni.

Ennek a három pontnak ugyanis…

Összesen csak két szomszédja van B-ben.

És az kicsit kevés.

Erről szól a Hall-tétel.

Legyen G(A, B, E) páros gráf és X pedig A-nak egy tetszőleges részhalmaza.

Az X-ben lévő csúcsok B-beli szomszédjainak halmazát hívjuk N(X)-nek.

A G gráfnak akkor és csak akkor van A-t fedő párosítása, ha bármely X halmazra

Hát, most úgy néz ki, ez nem teljesül.

X elemszáma ugyanis 3, N(X) elemszáma pedig csak 2.

Ebben a gráfban nincsen A-t fedő párosítás.

Egy bárban 60 lány van. Minden lány 12 fiút ismer és minden fiú 15 lányt ismer. Az ismertségek kölcsönösek. Hány fiú van a bában? Tudunk-e úgy fiú-lány párokat alkotni, hogy minden fiút egy ismerős lánnyal párosítunk?

Lányok

Minden lány 12 fiút ismer, és van 60 lány…

Összesen 720 él vezet a lányok halmazából a fiúk halmazába.

Fiúk

Minden fiú 15 lányt ismer.

Ha x darab fiú van, akkor a fiúkból kimenő élek száma:

Mivel az ismertségek kölcsönösek, ez pontosan ugyanannyi él, mint ahány él a lányokból kiindul.

A jelek szerint 48 fiú van.

Ha minden fiút egy ismerős lánnyal akarunk párosítani, akkor lennie kéne fiúkat fedő párosításnak.

Hát, nézzük, mit mond a Hall-tétel.

Vegyünk egy tetszőleges X halmazt B-ben.

Minden fiúnak 15 lány ismerőse van, ezért az X-ből kiinduló élek száma:

Az N(X) halmazban minden lánynak 12 ismerőse van, így az N(X)-be vezető élek száma:

Az nem kizárt, hogy N(X)-be máshonnan is mennek élek…

De az biztos, hogy X-ből minden él N(X)-be vezet.

Hiszen X-nek az összes szomszédja N(X)-ben van.

Így aztán N(X)-be legalább annyi él fut be, mint ahány él X-ből indul.

A Hall-tétel szerint létezik a fiúkat lefedő párosítás.

Egy kiránduláson fényképeket készítenek a résztvevőkről. Minden képen 4-en szerepelnek, és tudjuk, hogy mindenkiről legalább 4 kép készült. A kirándulás végén mindenki választhat egy képet. Igazoljuk, hogy biztosan mindenkinek jutni fog olyan kép, amin rajta van.

Résztvevők

Fényképek

Minden fényképnek pontosan 4 szomszédja van.

És minden résztvevőnek legalább 4.

Akkor jut mindenkinek biztosan fénykép, ha létezik a résztvevőket fedő párosítás.

Jöhet a Hall-tétel.

Vegyük a résztvevőknek egy X halmazát.

Mindenkiről legalább 4 kép készült, így az ebből kivezető élek száma:

Ezek a kivezető élek mind N(X)-be mennek.

És nem kizárt, hogy még máshonnan is mennek ide élek.

Minden fényképen 4 ember van, tehát az N(X)-be vezető élek száma:

fényképek száma

élek száma

Hopp, úgy tűnik teljesül a Hall-tétel.

Tehát létezik a résztvevőket fedő párosítás.