A gráfelmélet a matematika egyik legkifejezőbb ága, amely a hálózatok és struktúrák vizsgálatával foglalkozik. Ebben a modulban az alapfogalmakat sajátíthatod el. Megvizsgáljuk a kézfogási lemmát, elmélyedünk a reguláris és teljes gráfok szerkezetében, valamint megértjük a gráfok izomorfizmusát. Ezek a koncepciók elengedhetetlenek az emelt szintű érettségi kombinatorika feladatainak sikeres megoldásához.
1
Egy 8 pontú gráf minden csúcsának fokszáma 3. Hány éle van ennek a gráfnak?
A kézfogási lemma szerint a gráfban a fokszámok összege megegyezik az élek számának kétszeresével. A fokszámok összege $8 \cdot 3 = 24$. Így az élek száma $24 / 2 = 12$.
2
Hány éle van egy 12 csúcsú teljes gráfnak?
A $K_{12}$ teljes gráfban minden csúcs össze van kötve minden másik csúccsal. Az élek száma megegyezik a 12 csúcsból kiválasztható 2 elemű kombinációk számával: $\binom{12}{2} = \frac{12 \cdot 11}{2} = 66$.
3
Döntse el, hogy létezik-e olyan 5 csúcsú egyszerű gráf, amelynek a csúcsainak fokszámai: 1, 2, 3, 4, 4.
Nem létezik. Bár a fokszámok összege ($1+2+3+4+4=14$) páros, a két 4-es fokszámú csúcs az 5 csúcsú egyszerű gráfban minden más ponttal (így egymással is) össze van kötve. Emiatt a többi 3 pont mindegyike legalább a két 4-es fokszámú csúccsal szomszédos, azaz minden csúcs fokszáma legalább 2. Ez ellentmond annak, hogy van 1-es fokszámú csúcs.
4
Egy társaságban 15 ember van. Lehetséges-e, hogy mindenki pontosan 3 másik emberrel fogott kezet?
Nem lehetséges. Ha a helyzetet gráffal modellezzük, egy 15 csúcsú, 3-reguláris gráfot kapunk. Ennek fokszámösszege $15 \cdot 3 = 45$, ami páratlan. A kézfogási lemma alapján ez lehetetlen.
5
Két egyszerű gráf csúcsainak fokszámai egyenként megegyeznek. Biztosan izomorf a két gráf?
Nem feltétlenül. Például két 6 csúcsú, 3-reguláris gráf (mindkettő foksora $3, 3, 3, 3, 3, 3$) nem mindig izomorf. Az egyik lehet a $K_{3,3}$ teljes páros gráf (amely nem tartalmaz páratlan kört), a másik pedig egy olyan gráf, amely egy 3 hosszú körből épül fel. Strukturálisan eltérnek, így nem izomorfak.
6
Egy 7 csúcsú egyszerű gráfnak 10 éle van. Hány éle van a komplementer gráfnak?
Egy gráf és komplementere együtt egy teljes gráfot alkotnak. A 7 csúcsú teljes gráf éleinek száma $\binom{7}{2} = 21$. Így a komplementer gráf élszáma a hiányzó élek száma, azaz $21 - 10 = 11$.
7
Legfeljebb hány éle lehet egy 8 csúcsú egyszerű gráfnak, ha tudjuk, hogy nem összefüggő?
Ahhoz, hogy a gráf ne legyen összefüggő, legalább két komponensből kell állnia. A legtöbb élt akkor kapjuk, ha a két komponens teljes gráf, és az egyik mérete a lehető legnagyobb. Ha az egyik komponens a 7 csúcsú teljes gráf ($K_7$), a másik 1 izolált pont ($K_1$), akkor az élek száma $\binom{7}{2} = 21$.
8
Egy egyszerű páros gráf csúcsainak száma 10. Legfeljebb hány éle lehet?
A páros gráf csúcsait két diszjunkt halmazra oszthatjuk. Legyen az egyikben $k$, a másikban $10 - k$ elem. A maximális élszám a $K_{k, 10-k}$ esetén áll fenn, ami $k(10-k)$. Ez a másodfokú kifejezés a szimmetria miatt $k = 5$ esetén maximális. Az élszám maximuma: $5 \cdot 5 = 25$.
9
Egy összefüggő, körmentes gráfnak 12 csúcsa van. Határozza meg a csúcsok fokszámának összegét.
Az összefüggő, körmentes gráf egy fa. Egy $n$ csúcsú fának mindig $n - 1$ éle van. Ebben az esetben az élszám $12 - 1 = 11$. A kézfogási lemma alapján a fokszámok összege kétszerese az élek számának: $2 \cdot 11 = 22$.
10
Mely $n > 2$ esetén tartalmaz a $K_n$ teljes gráf Euler-kört?
Egy összefüggő gráfban pontosan akkor van Euler-kör, ha minden csúcsának fokszáma páros. A $K_n$ teljes gráfban minden csúcs fokszáma $n-1$. Ahhoz, hogy $n-1$ páros legyen, $n$-nek páratlannak kell lennie. Tehát $n = 3, 5, 7, \dots$ páratlan számok esetén létezik Euler-kör.
11
Egy 6 csúcsú gráf komplementere egy kör ($C_6$). Hány éle van az eredeti gráfnak?
A $C_6$ kör gráfnak 6 csúcsa és 6 éle van. Egy 6 csúcsú teljes gráf éleinek száma $\binom{6}{2} = 15$. Mivel az eredeti és a komplementer gráf élszáma kiadja a teljes gráf élszámát, az eredeti gráfnak $15 - 6 = 9$ éle van.
12
Egy gráf izomorf a komplementerével. Ha a gráfnak 5 csúcsa van, hány éle kell, hogy legyen?
Mivel a gráf izomorf a komplementerével, ugyanannyi élük van. Egy 5 csúcsú teljes gráf összesen $\binom{5}{2} = 10$ élet tartalmaz. A gráf éleinek száma tehát ennek pontosan a fele, vagyis $10 / 2 = 5$ él.
13
Egy 20 csúcsú gráfban 4 csúcs fokszáma 5, a többi csúcs fokszáma pedig azonos értékű. Határozza meg ezt a közös fokszámot, ha a gráf éleinek száma 34.
Legyen a maradék 16 csúcs azonos fokszáma $x$. A kézfogási lemma szerint: $4 \cdot 5 + 16 \cdot x = 2 \cdot 34$. Rendezve: $20 + 16x = 68$, amiből $16x = 48$, így $x = 3$.
14
Milyen minimális számú élet kell törölni a $K_{10}$ teljes gráfból ahhoz, hogy a kapott gráf minden csúcsának fokszáma páros legyen?
A $K_{10}$ gráfban minden csúcs fokszáma 9 (páratlan), összesen 10 ilyen csúcs van. Egyetlen él törlése mindig pontosan 2 csúcs fokszámát módosítja (csökkenti 1-gyel). Ahhoz, hogy 10 csúcs paritása megváltozzon, minimálisan $10 / 2 = 5$ élet kell törölni úgy, hogy a törölt élek függetlenek legyenek egymástól (egy teljes párosítást alkossanak).
15
Két fa gráfnak egyaránt 8 csúcsa van, és a csúcsaik maximális fokszáma is megegyezik. Biztos-e, hogy a két fa izomorf?
Nem biztos. A csúcsok száma és a maximális fokszám egyezése nem elegendő az izomorfizmushoz. Például az egyik fában a maximális (pl. 3-as) fokszámú csúcs a fa centrumában helyezkedik el, míg a másik fában közelebb egy falevélhez, így a két fa szerkezete és átmérője különbözhet.
16
Döntse el, hogy a $K_{3,3}$ gráf síkba rajzolható-e élek metszése nélkül.
Nem rajzolható síkba. A gráf a klasszikus "három ház, három kút" problémának felel meg, és a Kuratowski-tétel értelmében a $K_{3,3}$ alapvetően nem síkba rajzolható struktúra. Ezt az izomorfizmus is megőrzi.
17
Határozza meg azt a legkisebb csúcsszámot, amelyre létezik 4-reguláris egyszerű gráf.
Egy $n$ csúcsú egyszerű gráfban a maximális fokszám $n-1$. Így ahhoz, hogy 4-reguláris gráf lehessen, szükséges, hogy $4 \le n-1$, azaz $n \ge 5$. A legkisebb csúcsszám 5, az erre a csúcsszámra illeszkedő 4-reguláris gráf a $K_5$ teljes gráf.
18
Egy gráfnak 15 csúcsa és 10 éle van. Legalább hány összefüggő komponensből áll?
Egy $k$ komponensből álló, köröket nem tartalmazó gráfban (erdő) az élek száma $n - k$. Ha a gráfban körök is vannak, az élszám ennél nagyobb. Tehát az élek száma mindig teljesíti, hogy $e \ge n - k$. Behelyettesítve: $10 \ge 15 - k$, amiből $k \ge 5$. A gráf tehát legalább 5 komponensből áll.
19
Egy összefüggő gráfról tudjuk, hogy minden benne lévő kör páros hosszúságú. Milyen speciális tulajdonsággal rendelkezik ez a gráf?
A gráfelmélet egyik alapvető tétele szerint egy gráf pontosan akkor páros gráf, ha nem tartalmaz páratlan hosszúságú kört. Mivel itt minden kör páros, a gráf biztosan páros gráf, azaz csúcsai két olyan halmazra oszthatók, amelyeken belül nem futnak élek.
20
Döntse el, hogy létezik-e olyan egyszerű gráf, amelynek minden csúcsa különböző fokszámú.
Nem létezik. Egy $n$ csúcsú egyszerű gráfban a lehetséges fokszámok halmaza: $0, 1, \dots, n-1$. Ez pontosan $n$ érték. Viszont ha van olyan csúcs, amelynek fokszáma $n-1$ (mindenkivel szomszédos), akkor egyetlen csúcs fokszáma sem lehet 0 (mert már egy él befut hozzá az $n-1$ fokszámúból). Tehát a gráf csak az egyik végletet veheti fel, így maximum $n-1$ különböző érték osztható ki az $n$ csúcsra. A skatulyaelv miatt mindig lesz legalább két egyenlő fokszámú csúcs.