Diszkrét matematika 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.

 

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

04
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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.

Itt jön egy fantasztikus
Diszkrét matematika epizód.
Végül is miért ne néznél meg
még egy epizódot?
Hurrá, itt már nincs következő!

Hozzászólások

Még nincs hozzászólás. Legyél Te az első!