Érettségi típusú, szöveges problémák gráfelméleti modelljei és kapcsolatuk a kombinatorikával
A gráfelmélet és a kombinatorika szoros kapcsolata az emelt szintű érettségi vizsga egyik legfontosabb sarokköve. Ebben a modulban a való életből vett, szöveges problémák modellalkotásával foglalkozunk. Megvizsgáljuk a kézfogás-lemmát, az Euler- és Hamilton-utakat, a páros gráfok tulajdonságait, valamint az extremális gráfelmélet alapjait. Az összefüggések és feszítőfák megértése segít a strukturális gondolkodás elmélyítésében, és biztos alapot teremt a legösszetettebb bizonyítási feladatokhoz is.
1
Egy 6 fős társaságban mindenki pontosan 3 másik embert ismer. Döntse el, hogy lehetséges-e ez az állapot, ha az ismeretségek kölcsönösek.
Igen, lehetséges. A fokszámok összege $6 \cdot 3 = 18$, ami páros, így a kézfogás-lemma teljesül. Egy lehetséges konstrukció például a $K_{3,3}$ teljes páros gráf.
2
Egy 12 csapatos labdarúgó-bajnokságban minden csapat pontosan egyszer mérkőzik meg minden másik csapattal. Határozza meg a lejátszott mérkőzések összesített számát.
A mérkőzések számát a csúcsok közötti élek száma adja a 12 csúcsú teljes gráfban. Ezt a kombinatorika segítségével az $\binom{12}{2} = \frac{12 \cdot 11}{2} = 66$ képlettel számíthatjuk ki.
3
Egy tánciskolában 5 fiú és 5 lány van jelen. Minden fiú pontosan 3 lánnyal táncolt az este folyamán. Számítsa ki, hogy összesen hány fiú-lány táncpár alakult ki.
Ez a szituáció egy páros gráffal modellezhető. Az egyik halmazban a fiúk, a másikban a lányok vannak. Az élek számát megkapjuk, ha a fiúk számát megszorozzuk az egy fiúhoz tartozó élek (fokszámok) számával. Összesen $5 \cdot 3 = 15$ táncpár alakult ki.
4
Egy 10 csúcsú egyszerű gráfban 4 csúcs fokszáma 3, a többi csúcs fokszáma 4. Határozza meg a gráf éleinek számát.
A kézfogás-lemma értelmében a gráfban a fokszámok összege az élek számának kétszerese. A fokszámok összege $4 \cdot 3 + 6 \cdot 4 = 12 + 24 = 36$. A gráfnak így $\frac{36}{2} = 18$ éle van.
5
Egy informatikai hálózatban 8 számítógépet kötöttek össze úgy, hogy bármelyik gépről bármelyik másikra el lehet jutni, de nincsenek felesleges, köröket bezáró kapcsolatok. Állapítsa meg, hány kábelt használtak fel.
A leírt hálózat egy összefüggő, körmentes gráfot, vagyis egy fát alkot. Bármely $n$ csúcsú fának pontosan $n - 1$ éle van. Így a 8 gépet pontosan 7 kábel köti össze.
6
Egy 8 fős baráti társaságban mindenki pontosan 4 másik embert ismer. Számítsa ki, hány olyan emberpár van a társaságban, akik nem ismerik egymást.
A 8 csúcsú teljes gráf összes éle $\binom{8}{2} = 28$. A meglévő ismeretségek (élek) száma $8 \cdot 4 / 2 = 16$. Az ismeretlen párok számát a teljes élhálózat és a meglévő élek különbsége adja, ami $28 - 16 = 12$.
7
Egy múzeum folyosóhálózata egy 7 csúcsú összefüggő gráffal modellezhető. A csúcsok fokszámai rendre 2, 2, 4, 4, 4, 4, 4. Döntse el, hogy végig lehet-e menni a múzeum összes folyosóján úgy, hogy minden folyosót pontosan egyszer érintünk, és visszatérünk a kiindulási pontba.
Igen, bejárható. Egy összefüggő gráfban pontosan akkor van Euler-kör (zárt Euler-vonal), ha minden csúcsának fokszáma páros. Mivel a 2 és a 4 is páros szám, a feltétel teljesül.
8
Egy $4 \times 4$-es pontrács bal alsó sarkából a jobb felső sarkába haladunk úgy, hogy csak jobbra és felfelé léphetünk a szomszédos rácspontokra. Határozza meg az összes lehetséges legrövidebb útvonal számát.
A rács bal alsó sarkából a jobb felsőbe jutáshoz pontosan 3 lépést kell tennünk jobbra és 3 lépést felfelé (mivel a rács pontjai $4 \times 4$-esek, az intervallumok száma irányonként 3). A legrövidebb útvonalak számát az ismétléses permutációk vagy a binomiális együtthatók adják meg, az eredmény $\binom{6}{3} = 20$.
9
Egy 6 fős társaságból egy 3 fős bizottságot kell kiválasztani. Számítsa ki, hányféleképpen tehető ez meg.
A kiválasztás sorrendje nem számít, ezért kombinációt alkalmazunk. A 6 emberből 3-at $\binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$ különböző módon lehet kiválasztani.
10
Egy 15 fős osztály tanulóit két csapatra osztják egy sportversenyhez. Mindenki csak a másik csapat tagjaival mérkőzik meg. Határozza meg, legfeljebb hány mérkőzést játszhatnak összesen.
A probléma egy páros gráffal írható le. Az élek (mérkőzések) száma akkor maximális, ha a két csapat létszáma a lehető legközelebb van egymáshoz. Ez egy 7 és egy 8 fős csapatot jelent, így a mérkőzések maximális száma $7 \cdot 8 = 56$.
11
Egy 20 fős társaságban bármely két ember vagy ismeri egymást, vagy van közös ismerősük. Állapítsa meg, legalább hány ismeretség (él) van a társaságban.
A feltétel azt jelenti, hogy a társaságot modellező gráf összefüggő. Egy összefüggő 20 csúcsú gráfnak legalább annyi éle kell legyen, mint egy feszítőfának. Egy 20 csúcsú fának minimálisan $20 - 1 = 19$ éle van.
12
Egy 7 csúcsú teljes gráf éleit piros és kék színnel színezzük. Határozza meg, összesen hány különböző háromszög (3 csúcsú kör) található a gráfban a színezéstől függetlenül.
A háromszögek száma független az élek színezésétől, hiszen a teljes gráf bármely 3 csúcsa összeköttetésben áll egymással. Ezt a 7 csúcsból 3 kiválasztásával számoljuk ki, az eredmény $\binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$.
13
Egy gráf csúcsainak száma 7, fokszámaik pedig rendre 1, 2, 2, 3, 3, 3, 5. Döntse el, hogy létezhet-e ilyen egyszerű gráf.
Nem létezhet. A kézfogás-lemma alapján egy gráfban a páratlan fokszámú csúcsok számának mindig párosnak kell lennie. Ebben a felsorolásban azonban pontosan 5 darab páratlan fokszám (1, 3, 3, 3, 5) található.
14
Egy futárszolgálatnak 5 várost kell meglátogatnia. Bármely két város között van közvetlen út. Határozza meg, hányféleképpen tervezheti meg az útvonalát úgy, hogy minden várost pontosan egyszer érintsen.
A városokat sorban kell meglátogatni, ami a csúcsok egy permutációját jelenti. Az 5 város sorrendjét $5! = 120$ különböző módon lehet meghatározni (ez felel meg a Hamilton-utak számának a $K_5$ gráfban, irányított útvonalként tekintve).
15
Egy 9 fős baráti társaságban mindenki pontosan ugyanannyi embert ismer a társaságból. Adja meg a lehetséges értékeket erre a közös ismeretségszámra.
A társaság egy 9 csúcsú reguláris gráffal modellezhető. A kézfogás-lemma miatt a $9 \cdot k$ (ahol $k$ a közös ismeretségszám) páros kell legyen. Ez csak akkor lehetséges, ha $k$ páros szám. A lehetséges értékek így a 0, 2, 4, 6 és 8.
16
Egy síkba rajzolható egyszerű gráf 10 csúccsal és 15 éllel rendelkezik. Határozza meg, hány tartományra osztja a síkot ez a gráf.
Az Euler-féle poliédertétel síkgráfokra vonatkozó alakja szerint $c - e + t = 2$, ahol $c$ a csúcsok, $e$ az élek, $t$ a tartományok száma (beleértve a külső tartományt is). Behelyettesítve $10 - 15 + t = 2$, amiből $t = 7$ adódik.
17
Egy 10 csúcsú egyszerű gráf nem tartalmaz háromszöget (vagyis nincs 3 olyan csúcsa, amelyek páronként össze lennének kötve). Határozza meg, legfeljebb hány éle lehet a gráfnak.
Turán tétele alapján, ha egy $n$ csúcsú egyszerű gráf nem tartalmaz háromszöget, akkor az élek száma legfeljebb $\frac{n^2}{4}$ lehet. $n=10$ esetén ez $\frac{100}{4} = 25$ élt jelent. (Ezt a maximumot a $K_{5,5}$ teljes páros gráf éri el).
18
Egy 4 csúcsú teljes gráfnak hány különböző feszítőfája létezik, feltételezve, hogy a csúcsok megkülönböztethetők.
A megkülönböztethető csúcsokból álló teljes gráfok feszítőfáinak számát a Cayley-formula adja meg, amely $n^{n-2}$. Mivel $n=4$, a behelyettesítés után kapjuk, hogy $4^{4-2} = 4^2 = 16$.
19
Egy összefüggő gráf minden csúcsának fokszáma páros. A gráfot kiegészítjük egy új csúccsal, amelyet pontosan 3 régi csúccsal kötünk össze. Döntse el, hogy az új gráfban lehetséges-e minden élt pontosan egyszer bejárni egy folytonos vonallal.
Nem lehetséges. Az eredeti gráfban minden csúcs foka páros volt. Az új csúcs (amelynek fokszáma 3) páratlan fokú lesz, és a hozzá kötött 3 eredeti csúcs fokszáma is páratlanná válik. Így összesen 4 páratlan fokú csúcs lesz, míg az Euler-vonal létezéséhez (ami egy folytonos élbejárást jelent) legfeljebb 2 lehetne.
20
Egy sakkbajnokságon minden résztvevő pontosan egyszer játszik mindenki mással. Összesen 120 mérkőzést játszottak a verseny során. Határozza meg a résztvevők számát.
A mérkőzések száma egy $n$ csúcsú teljes gráf éleinek számával egyezik meg. A $\frac{n(n-1)}{2} = 120$ egyenletet felírva az $n^2 - n - 240 = 0$ másodfokú egyenletet kapjuk. Ennek pozitív gyöke $n = 16$, tehát pontosan 16 játékos vett részt a bajnokságon.