Diszkrét matematika epizód tartalma:
A páros gráfok teljes párosításáról szól a Frobenius tétel. Nézzük meg, hogyan működik és oldjunk meg néhány feladatot a Frobenius tétel segítségével.
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.
Diszkrét matematika epizód.