Barion Pixel Párosítás feladatok páros gráfokban | mateking
 

Számítástudomány epizód tartalma:

Páros gráfokkal kapcsolatos feladatok lépésről lépésre. Megnézzük, hogyan kell használni a Hall-feltételt és a Frobenius tételt.

A képsor tartalma

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.

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • Jó árban van és hihetetlenül világos a magyarázat és annyiszor lehet visszatérni az egyes lépésekre, ahányszor arra csak szükség van a megértéshez.

    Lili, 22
  • Otthonról elérhető és olcsóbb, mint egy magántanár és akkor használom, amikor akarom.

    Milán, 19
  • Értelmes, szórakoztató, minden pénzt megér.

    Tibor, 23
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez