Bevezetés a számításelméletbe 2 epizód tartalma:
Nézd meg, hogy mi az a Hall-feltétel, hogyan kell használni és hogyan lehet a Hall-tétel segítségével páros gráfokban A-t vagy B-t fedő párosításokat találni.
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.
Bevezetés a számításelméletbe 2 epizód.