Jump to navigation

Belépés
  • Elfelejtettem a jelszavam
Regisztráció
 
  • Hogyan működik a mateking?
  • Mire jó a matek?
  • Matek érettségi
  • Képletgyűjtemény
  • Feladatgyűjtemény
  • Rólunk
  • Matek 5. osztály próbaüzem
  • Matek 6. osztály próbaüzem
  • Matek 7. osztály próbaüzem
  • Matek 8. osztály próbaüzem
  • Matek 9. osztály
  • Matek 10. osztály
  • Matek 11. osztály
  • Matek 12. osztály
  • Középiskolai matek (teljes)
  • Középszintű matek érettségi
  • Emelt szintű matek érettségi
  • Egyetemi matek alapozó
Összes egyetemi tantárgy
Legnépszerűbb tantárgyak:
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Valószínűségszámítás
  • Lineáris algebra
  • Diszkrét matematika
  • Statisztika

mateking

Login
 

Bevezetés a számításelméletbe 2

Kategóriák
  • 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

  • Epizódok
  • Feladatok
  • Képletek
01
 
Páros gráfok, párosítások
02
 
A Hall tétel
03
 
Frobenius tétele
04
 
Párosítás feladatok páros gráfokban
05
 
FELADAT | Páros gráfok, párosítások
06
 
FELADAT | Páros gráfok, párosítások
07
 
FELADAT | Páros gráfok, párosítások
08
 
FELADAT | Páros gráfok, párosítások
09
 
FELADAT | 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 \)

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

1.

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.

Megnézem, hogyan kell megoldani

2.

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.

Megnézem, hogyan kell megoldani

3.

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} \)

Megnézem, hogyan kell megoldani

4.

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.

Megnézem, hogyan kell megoldani

5.

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?

Megnézem, hogyan kell megoldani

6.

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?

Megnézem, hogyan kell megoldani

7.

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.

Megnézem, hogyan kell megoldani

8.

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.

Megnézem, hogyan kell megoldani

A témakör tartalma


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

Kapcsolatfelvétel
  • Segítségnyújtás
  • Hibabejelentés
  • Kapcsolatfelvétel
  • Mateking torrent bejelentés
Rólunk
  • A projektről
  • Médiamegjelenések
  • Legyen élmény a matek
  • Mire jó a matek?
Tartalomjegyzék
  • Középiskolai matek
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Lineáris algebra
  • Valószínűségszámítás
  • Diszkrét matematika
  • Statisztika
  • További tantárgyak
  • Egyetemi tematikák
  • Matek érettségi
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

Cookie-használat módosítása

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!

barion
macroweb
  • Tantárgyaim