Gráfelmélet Bevezető

A gráfok világa: csúcsok, élek és alapfogalmak

A gráfelmélet a diszkrét matematika egyik legizgalmasabb és leglátványosabb ága, amely hálózatok, kapcsolatrendszerek és bonyolult struktúrák modellezésével foglalkozik. Akár az internet működését, az úthálózatokat, vagy a közösségi média ismerősi kapcsolatait vizsgáljuk, mindenhol gráfokkal találkozunk. A sikeres emelt szintű matematika érettségi elképzelhetetlen ezen alapfogalmak mély és magabiztos ismerete nélkül. Ebben a leckében lépésről lépésre, vizuális ábrákon keresztül építjük fel a gráfelmélet legfontosabb alapköveit, hogy az elmélet ne egy száraz definícióhalmaz legyen, hanem egy logikus és átlátható rendszer.

Mi az a gráf? Alapvető definíciók

Matematikai értelemben a gráf nem más, mint pontok (csúcsok) és az azokat összekötő vonalak (élek) halmaza. Egy $G$ gráfot formálisan egy $G = (V, E)$ rendezett párként definiálunk, ahol:

  • $V$ (Vertices - Csúcsok): A gráf pontjainak, elemeinek nem üres halmaza. Gyakran nagybetűkkel jelöljük őket, például $A, B, C$.
  • $E$ (Edges - Élek): A csúcsokat összekötő kapcsolatok halmaza. Egy él pontosan két csúcsot köt össze.

A gráfelméletben a csúcsok pontos geometriai elhelyezkedése (hogy hol vannak a papíron), vagy az élek alakja (hogy egyenesek vagy görbék) teljesen lényegtelen. Kizárólag a kapcsolódások (szomszédság) ténye számít. Két csúcsot szomszédosnak nevezünk, ha vezet közöttük él.

A B C D

1. ábra: Egy egyszerű gráf 4 csúccsal ($V = \{A, B, C, D\}$) és 4 éllel.

A fenti ábrán látható gráfban az $A$ és $B$ csúcsok szomszédosak, viszont $A$ és $D$ között nincs közvetlen kapcsolat, így ők nem szomszédosak. Az ilyen vizuális reprezentáció segít a feladatok átláthatóvá tételében, különösen kombinatorikai problémák esetében.

A csúcsok fokszáma és a kézfogás-lemma

Egy $v$ csúcs fokszáma (jelölése: $d(v)$ a *degree* szóból) megadja, hogy az adott csúcsba hány él fut be (vagy indul ki onnan). Ha egy él két különböző csúcsot köt össze, akkor mindkét csúcs fokszámát egyel növeli. Ha a gráfban nincsenek többszörös élek vagy hurkok, a fokszám pontosan megegyezik a csúcs szomszédainak számával.

1 d=2 2 d=3 3 d=3 4 d=2

2. ábra: A csúcsok fokszámai jól láthatóan megadják a beléjük futó élek számát.

A gráfelmélet egyik legfontosabb és az érettségin is gyakran előkerülő tétele a kézfogás-lemma. Képzeljük el, hogy egy társaságban az emberek kezet fognak egymással. Minden egyes kézfogás (él) pontosan két embert (csúcsot) érint. Ebből logikusan következik a tétel:

Kézfogás-lemma: Bármely gráfban a csúcsok fokszámainak összege megegyezik az élek számának kétszeresével. $$\sum_{v \in V} d(v) = 2 \cdot |E|$$

Ebből a képletből származik egy nagyon fontos következmény is: A páratlan fokszámú csúcsok száma minden gráfban páros kell, hogy legyen. Ha egy feladatban például azt kérdezik, hogy "Létezik-e olyan gráf, amiben pontosan 3 darab páratlan fokszámú csúcs van?", a válasz a kézfogás-lemma alapján azonnal rávágható, hogy nem létezik.

Egyszerű gráfok: Hurkok és többszörös élek

A gimnáziumi tananyagban és az érettségi feladatokban az esetek 99%-ában úgynevezett egyszerű gráfokkal dolgozunk. De mitől lesz egy gráf "egyszerű"? Egy gráfot akkor nevezünk egyszerűnek, ha teljesül rá két fontos feltétel:

  • Nincsenek benne hurokélek: A hurokél olyan él, amelynek mindkét végpontja ugyanaz a csúcs (a csúcs "önmagával" van összekötve).
  • Nincsenek benne többszörös (párhuzamos) élek: Két csúcs között legfeljebb csak egyetlen él haladhat.
Nem egyszerű gráf Egyszerű gráf

3. ábra: Különbség a többszörös éllel és hurokéllel rendelkező gráf, valamint az egyszerű gráf között.

Ha egy feladat kiemeli, hogy a gráf "egyszerű", akkor tudjuk, hogy egy $N$ csúcsú gráfban egy csúcs maximális fokszáma legfeljebb $N-1$ lehet, hiszen önmagát leszámítva minden más csúccsal legfeljebb egy élen keresztül lehet összekötve. Ebből adódik a Teljes gráf fogalma is, melyben minden csúcs össze van kötve minden másik csúccsal.