Páros gráfok, párosítások

A témakör tartalma

Gyorsan és szuper-érthetően megtudhatsz mindent a páros gráfokról, párosításokról, a páros gráf pontosztályait fedő párosításokról és még sok minden másról... 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. Majd megtudhatod, hogy a páros gráfok teljes párosításáról szól a Frobenius tétel. Megnézzük, hogyan működik és oldjunk meg néhány feladatot a Frobenius tétel segítségével. Végezetül pedig jönnek majd páros gráfokkal kapcsolatos feladatok lépésről lépésre és megnézzük, hogyan kell használni a Hall-feltételt és a Frobenius tételt.



Páros gráfok, párosítások

Páros gráfokról már korábban is volt szó.

Most viszont csak róluk lesz szó, úgyhogy próbáljuk meg egy kis hipnózis segítségével fölidézni, miket is kéne tudnunk a páros gráfokról.

Egy G gráf páros gráf, ha csúcsainak a V(G) halmaza felbontható az A és B diszjunkt részhalmazokra úgy…

hogy A-n és B-n belül nem vezetnek élek.

Az ilyen gráfokat úgy fogjuk jelölni, hogy V(A, B, E).

Itt A és B a gráf csúcsainak két diszjunkt halmaza, E pedig a köztük vezető élek halmaza.

Egy G gráf páros gráf, ha csúcsainak a V(G) halmaza felbontható az A és B diszjunkt részhalmazokra úgy, hogy A-n és B-n belül nem vezetnek élek.

A páros gráf jelölées: V(A, B, E).

Aztán volt még itt más is…

Azt is megnéztük, hogy egy G gráf pontosan akkor páros, ha minden G-ben szereplő kör páros hosszúságú.

Egy G gráf akkor és csak akkor páros,

ha minden G-ben szereplő kör páros hosszúságú.

És végül még egy dolog…

Egy G gráfban az E(G) élhalmaznak egy M részhalmazát párosításnak nevezzük, ha M semelyik két elemének nincs közös végpontja.

Ez itt például egy párosítás.

Ez a párosítás egy A-t fedő párosítás, mert a benne szereplő élek A-nak minden csúcsát lefogják.

És egyúttal B-t fedő párosítás is.

Ha a gráfon kisebb átalakítást végzünk…

Akkor már nehezebb A-t fedő párosítást találni.

De azért van.

Ebben a gráfban viszont…

Biztosan nem létezhet B-t fedő párosítás.

Vagy B4-et párosítjuk A4-gyel…

vagy pedig B3-at.

De mindkettőt egyszerre nem lehet.

És nincsen A-t fedő párosítás sem.

Vagy A2-t fedjük le…

vagy A3-at.

Mindkettőt egyszerre nem lehet.

Olyankor, amikor a gráf egy kicsit bonyolultabb…

néha bizony nehéz eldönteni, hogy létezik-e A-t vagy B-t lefedő párosítás.

Szerencsére mindjárt jön néhány tétel, ami segít tisztázni ezeket a kínzó kérdéseket.

Nehogy egész éjjel álmatlanul forgolódjunk emiatt.


A Hall tétel

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.


Frobenius tétele

Van itt ez a G(A, B, E) páros gráf.

Ha A-ban és B-ben ugyanannyi csúcs van és létezik A-t fedő párosítás…

akkor az nyilván B-t is fedi, így van a gráfban teljes párosítás.

Ezt a nem túl bonyolult dolgot mondja ki Frobenius tétele.

Frobenius tétele:

A G(A, B, E) páros gráfban akkor és csak akkor létezik teljes párosítás, ha

  és

teljesül a Hall-tétel.

Utóbbit akár egy kicsit részletezhetjük is.

Most pedig nézzük, mire is használhatnánk Frobenius tételét, jóra vagy rosszra…

Egy bálon 10 fiú és 10 lány vesz részt. Minden lány legalább 6 fiút ismer és minden fiú is legalább 6 lányt. Az ismertségek kölcsönösek. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.

Ugyanannyi lány van, mint fiú, tehát az első feltétel meg is van.

Nézzük, mi a helyzet a másodikkal.

Itt egy hasznos kis trükköt fogunk használni.

Azért nem olyan nagy trükk.

Nézzük először azokat az X halmazokat, amik legfeljebb 6 eleműek.

Mivel X-ben már egyetlen pontnak is legalább 6 szomszédja van, így nyilván

Ezekre az X halmazokra teljesül a Hall-feltétel.

Most nézzük, mi van akkor, ha

Ekkor az A\X halmazban legfeljebb 3 elem van.

De B-ben mindenkinek legalább 6 szomszédja van.

Ez pedig csak úgy jön ki, ha B minden pontjának van szomszédja X-ben.

Vagyis B=N(X).

Ezek szerint N(X) 10 elemű.

Így biztosan teljesül a Hall-feltétel.

Fergeteges nyitótáncra lehet tehát számítani…

Egy 12 csúcsú páros gráfban minden csúcs foka 3 vagy 4. Bizonyítsuk be, hogy van a gráfban teljes párosítás.

Íme, a gráf.

Igazán remek lenne megint a Frobenius tételt használni, ezért azzal kezdjük, hogy igazoljuk: |A|=|B|.

Ha A-ban mondjuk csak 5 pont lenne…

És mindegyik pont foka a lehető legtöbb, vagyis 4…

akkor 20 él indul útnak A-ból.

B-ben ekkor 7 csúcs van, és ha mindegyik foka a lehető legkisebb…

az is 21 darab él.

Hát, ez így nem jön ki.

Még így is kevesebb él indul útnak A-ból, mint amennyinek B-be érkeznie kellene.

A-ban 5-nél több csúcsnak kell lennie…

Na és persze B-ben is.

Ez azt jelenti, hogy mindkét pontosztályban 6 csúcs van.

Eddig jó.

Most nézzük, mi van a szomszédokkal.

Ha X legfeljebb 3 elemű, akkor biztosan teljesül a Hall-feltétel.

Mert X-ben minden pontnak legalább 3 szomszédja van, ezért N(X)-ben is van legalább 3 pont.

Nézzük mi van akkor, ha X-nek 4 eleme van…

B-ben mindenkinek legalább 3 szomszédja van.

Ez pedig csak úgy jön ki, ha B minden pontjának van szomszédja X-ben.

Vagyis ilyenkor B=N(X).

Úgy néz ki, ilyenkor is teljesül a Hall-feltétel.

Ha pedig X 5 vagy 6 elemű, akkor pláne.

Vagyis létezik a gráfban teljes párosítás.


Párosítás feladatok páros gráfokban

Egy bálon összesen 16-an vesznek részt, lányok és fiúk. Minden lány vagy 4 vagy 5 fiút ismer és minden fiú is vagy 4 vagy 5 lányt. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.

Igazán remek lenne a Frobenius tételt használni, ezért azzal kezdjük, hogy igazoljuk: |A|=|B|.

Ha nem ugyanannyi csúcs van mindkét halmazban, akkor az egyikben kevesebb van…

Nézzük, mi lenne akkor, ha A-ban mondjuk csak 7 pont lenne…

És B-ben pedig 9.

Hogyha A-ban mindegyik pont foka a lehető legtöbb, vagyis 5…

akkor 35 él indul útnak A-ból.

B-ben ekkor 9 csúcs van, és ha mindegyik foka a lehető legkisebb…

már az is 36 darab él.

Tehát még így is kevesebb él indul útnak A-ból, mint amennyinek B-be érkeznie kellene.

Muszáj, hogy A-ban több pont legyen…

Ez azt jelenti, hogy mindkét pontosztályban 8 csúcs van.

Eddig jó.

Most nézzük, mi van a szomszédokkal.

Vegyünk egy X részhalmazt az A-ban.

Ha X legfeljebb 4 elemű, akkor biztosan teljesül a Hall-feltétel.

Mert X-ben minden pontnak legalább 4 szomszédja van, ezért N(X)-ben is van legalább 4 pont.

Nézzük mi van akkor, ha X-nek 5 eleme van…

B-ben mindenkinek legalább 4 szomszédja van.

Ez pedig csak úgy jön ki, ha B minden pontjának van szomszédja X-ben.

Vagyis ilyenkor B=N(X).

Úgy néz ki, ilyenkor is teljesül a Hall-feltétel.

Ha pedig X 6 vagy 7 vagy elemű, akkor pláne.

Vagyis létezik a gráfban teljes párosítás.

Fergeteges nyitótáncra lehet tehát számítani…

Egy páros gráf két pontosztálya A és B. Két pont akkor szomszédos, ha ebben a szomszédsági mátrixban az A-ban lévő pont sorának és a B-ben lévő pont oszlopának metszetében 1-es áll.

Van-e a gráfban teljes párosítás?

Hát, nézzük, teljesül-e a Hall-feltétel.

Itt van, mondjuk ez az X halmaz.

A hozzá tartozó N(X) pedig…

Hopp, úgy tűnik az egész B.

Van persze olyan X is…

hogy az N(X) nem a teljes B halmaz, csak egy része.

A nagy kérdés persze az, hogy bárhogyan választunk is X-et, vajon mindig teljesülni fog-e, hogy

Ezt egyesével végignézni kicsit sokáig tartana.

Inkább próbáljunk találni egy teljes párosítást.

Ehhez minden sorban és oszlopban pontosan egy darab 1-est kell tudnunk választani…

Ilyen úgy tűnik, van.

Tehát létezik a gráfban teljes párosítás.

Egy másik G páros gráf két pontosztálya A és B. Két pont akkor szomszédos, ha ebben a szomszédsági mátrixban az A-ban lévő pont sorának és a B-ben lévő pont oszlopának metszetében 1-es áll. Van-e G-ben teljes párosítás?

Ebben a gráfban néhány a-nak feltűnően kevés szomszédja van…

Így aztán hátha nem teljesül rájuk a Hall-feltétel.

Nekik, például legfeljebb csak két szomszédjuk van.

Nézzük meg, hogy pontosan kik ezek.

Hát sajnos a szomszédok is 4-en vannak, így a Hall-feltétel teljesül.

De ha találunk egy újabb csúcsot A-ban, aminek csak olyan szomszédjai vannak B-ben, amik már korábban is kijöttek…

Hát, ez nem ilyen.

De ez…

Na, ez ilyen.

Van olyan X halmaz A-ban, amire nem teljesül, hogy

Így aztán nem teljesül a Hall-feltétel és nincs a gráfban teljes párosítás.

 eddig is.

ebben a gráfban 4 független él is…

De már az elején sikerült belenyúlnunk egy olyan élbe…

ami annyira szerencsétlenül helyezkedik el, hogy csak 3 független élig tudunk eljutni.


FELADAT | Páros gráfok, párosítások

FELADAT | Páros gráfok, párosítások

FELADAT | Páros gráfok, párosítások

FELADAT | Páros gráfok, párosítások

FELADAT | Páros gráfok, párosítások