- Kombinatorika
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
Páros gráfok, párosítások
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
\( \mid X \mid \leq \mid N(X) \mid \)
Frobenius tétele
A $G(A, B, E)$ páros gráfban akkor és csak akkor létezik teljes párosítás, ha
$ \mid A \mid = \mid B \mid$ és
$ \mid X \mid \leq \mid N(X) \mid $ minden $X \subseteq A $ ponthalmazra.
a) 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árban? Tudunk-e úgy fiú-lány párokat alkotni, hogy minden fiút egy ismerős lánnyal párosítunk?
b) Egy kiránduláson fényképet 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.
a) 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.
b) 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.
a) Egy bálon összesen 16-an vesznek részt. 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.
b) 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:
\( \begin{matrix} & b_1 & b_2 & b_3 & b_4 & b_5 & b_6 & b_7 \\ a_1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ a_2 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ a_3 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ a_4 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ a_5 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ a_6 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ a_7 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix} \)
Van-e a gráfban teljes párosítás?
c) 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?
\( \begin{matrix} & b_1 & b_2 & b_3 & b_4 & b_5 & b_6 & b_7 \\a_1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\a_2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\a_3 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\a_4 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\a_5 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\a_6 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\a_7 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \end{matrix} \)
Egy 20 csúcsú egyszerű páros gráfban minden fok 5 vagy 6. Mutassuk meg, hogy a gráfnak van teljes párosítása.
Egy bálon 12 lány és 666 fiú vesz részt. A szervezők így 12 (fiú-lány) párt szeretnének összeállítani a nyitótánchoz úgy, hogy mindenki ismerőssel táncoljon. Minden lány legalább 11 fiút ismer, a fiúk közül viszont mindenki legfeljebb 11 lányt ismer. Biztosan össze tudják-e állítani a szervezők a 12 párt?
Egy bálon 1001 lány és 1001 fiú vesz részt, mindenkinek legalább 500 ellenkező nemű ismerőse van. Biztosan össze lehet-e állítani 1001 olyan fiú-lány párt, ahol a párok tagjai ismerősök?
Egy G egyszerű, páros gráf mindkét színosztálya egyenként 999 pontot tartalmaz, az A színosztályban minden pont foka legalább 666, B-ben pedig legalább 333. Mutassuk meg, hogy G-nek van teljes párosítása.
Egy G egyszerű, páros gráf A színosztályában 99 csúcsa van, ezek bármelyikének a fokszáma legalább 33, de A-ban van 66 olyan csúcs, amelyek bármelyikének foka legalább 66. Sőt, A tartalmaz 33 olyan csúcsot is, amelyek mindegyikéből legalább 99 él indul. Mutassuk meg, hogy G-nek van A-t fedő párosítása.
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.
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.
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.
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.
