1.4 Gráfelmélet

A gráfelmélet pontok és az azokat összekötő élek matematikai vizsgálatával foglalkozik. Az emelt szintű érettségi az alábbi fogalmak precíz ismeretét követeli meg:

• Gráf és Egyszerű gráf: A gráf pontok (csúcsok) és élek halmaza. Egy gráfot egyszerűnek nevezünk, ha nem tartalmaz hurokélt (olyan élt, ami egy pontot önmagával köt össze) és többszörös élt (két pont között legfeljebb egy él fut).
• Fokszám: Egy adott pontba futó élek száma. Hurokél esetén az adott él kétszer számít bele a fokszámba.
• Séta, Út és Kör: A séta pontok és élek váltakozó sorozata. Ha egy sétában minden pont legfeljebb egyszer szerepel, akkor útnak nevezzük. Ha a séta kezdő- és végpontja megegyezik (legalább 3 hosszú), és a közbenső pontok nem ismétlődnek, akkor körről (vagy körsétáról) beszélünk.
• Összefüggő gráf és Fa: Egy gráf összefüggő, ha bármely két pontja között vezet út. A fa olyan összefüggő gráf, amely nem tartalmaz kört.
• Teljes gráf és Komplementer gráf: Az $n$ pontú teljes gráfban bármely két különböző pont össze van kötve. Egy $G$ gráf komplementere ugyanazokon a pontokon értelmezett gráf, amelyben két pont pontosan akkor van összekötve, ha az eredeti $G$-ben nem voltak.
• Izomorf gráfok: Két gráf izomorf, ha szerkezetileg azonosak, azaz létezik a pontjaik között egy olyan kölcsönösen egyértelmű megfeleltetés (bijekció), amely tartja az éleket.

1. Tétel (A fokszámok összege): Bármely gráfban a pontok fokszámának összege megegyezik az élek számának kétszeresével. Ebből következik, hogy a páratlan fokszámú pontok száma mindig páros.

2. Tétel (Speciális gráfok élszáma):

• Az $n$ pontú teljes gráf éleinek száma: $|E| = \binom{n}{2} = \frac{n(n-1)}{2}$.
• Az $n$ pontú fa éleinek száma pontosan: $|E| = n - 1$.

Tétel Bizonyítással: Bármely (legalább kétpontú) egyszerű gráfban létezik két azonos fokszámú pont.

Bizonyítás (Skatulya-elvvel):

Tegyük fel, hogy van egy $n$ pontú egyszerű gráfunk ($n \ge 2$). Mivel a gráf egyszerű (nincs hurokél, sem többszörös él), egy adott pont fokszáma minimálisan $0$ (izolált pont), maximálisan pedig $n-1$ (minden más ponttal össze van kötve) lehet.

A lehetséges fokszámok halmaza tehát: $\{0, 1, 2, \dots, n-1\}$. Ez összesen $n$ darab különböző lehetséges érték.

Azonban a $0$ és az $n-1$ fokszám nem fordulhat elő egyszerre ugyanabban a gráfban. Ha ugyanis van egy $n-1$ fokszámú pont, az az összes többi ponttal össze van kötve, így egyetlen más pont sem lehet $0$ fokszámú (izolált). Fordítva: ha van $0$ fokszámú pont, az senkivel sincs összekötve, így nem lehet $n-1$ fokszámú pont sem.

Emiatt a gráfban ténylegesen kiosztható fokszámok vagy a $\{0, 1, \dots, n-2\}$ halmazból, vagy az $\{1, 2, \dots, n-1\}$ halmazból kerülnek ki. Mindkét halmaz pontosan $n-1$ elemet tartalmaz.

Mivel a gráfunknak $n$ darab pontja van (ezek a "galambok"), de legfeljebb $n-1$ különböző fokszámot tudunk nekik adni (ezek a "skatulyák"), a skatulya-elv alapján biztosan kell lennie legalább két olyan pontnak, amelyek ugyanabba a skatulyába kerülnek, azaz a fokszámuk megegyezik. $\blacksquare$

Történet: A gráfelmélet születését 1736-ra tehetjük, amikor Leonhard Euler svájci matematikus megoldotta a híres königsbergi hidak problémáját. A városban hét híd ívelt át a Pregel folyón. A kérdés az volt, végig lehet-e menni úgy a városon, hogy minden hídon pontosan egyszer haladjunk át. Euler a földdarabokat pontokkal, a hidakat élekkel modellezte, és bebizonyította, hogy mivel több mint kettő páratlan fokszámú pont (földdarab) van, ilyen séta nem létezik (az ilyen utat ma Euler-vonalnak hívjuk).

Gyakorlati Alkalmazás: Ma a gráfelmélet átszövi a mindennapjainkat. A GPS navigációs rendszerek (útvonaltervezés) a városokat gráfként értelmezik, és a legrövidebb utat keresik bennük (pl. Dijkstra-algoritmus). Ugyanígy gráfokon alapul a számítógépes hálózatok (pl. az Internet) topológiája, a kémiai molekulák modellezése, és a közösségi média hálózatok elemzése is, ahol az izomorfizmus és az összefüggőség vizsgálata segít a közösségek és az információterjedés megértésében.

Egy $G$ egyszerű gráfról tudjuk, hogy 8 pontja van és fa gráf. Határozza meg a $G$ gráf komplementerének élszámát!