Gráfelméleti alapfogalmak, fokszámok, Havel–Hakimi-tétel

Definíció — irányítatlan gráf

Legyen \(V \neq \emptyset\) véges halmaz, \(E\) véges halmaz, és \(\varphi: E \to \mathcal{P}_{\le 2}(V)\) egy leképezés (amely \(V\) 1 vagy 2 elemű részhalmazaiba képez). Ekkor a \(G = (V, E, \varphi)\) hármast (irányítatlan) gráfnak nevezzük.

• \(V\) elemei: \(G\) gráf csúcsai (vertex).
• \(E\) elemei: \(G\) gráf élei (edge).
• \(\varphi\) neve: illeszkedési függvény.

Ha \(e \in E\) és \(\varphi(e) = \{v, w\}\), akkor azt mondjuk, hogy:

• \(e\) él végpontjai \(v, w\),
• \(e\) él illeszkedik \(v, w\)-re / \(v, w\) illeszkedik \(e\)-re,
• \(e\) él köti össze \(v, w\)-t,
• \(e\) él a \(v, w\) csúcsok között vezet.

Definíció — szomszédos csúcsok

A \(v, w \in V\) csúcsok szomszédosak, ha vezet közöttük él.

Definíció — hurokél és párhuzamos élek

Egy \(G = (V, E, \varphi)\) gráfban egy \(e\) él hurokél, ha \(|\varphi(e)| = 1\) (\(e \in E\)). Az \(e, f \in E\) élek párhuzamos élek, ha \(\varphi(e) = \varphi(f)\).

Definíció — egyszerű gráf

Egy gráf egyszerű gráf, ha nincs benne sem hurokél, sem párhuzamos él.

Definíció — csúcs fokszáma

Egy \(G\) gráfban \(v \in V(G)\) csúcs fokszáma a \(v\)-re illeszkedő élek száma úgy, hogy a hurokéleket kétszer számoljuk. Jelölése: \(d(v)\) (degree).

Definíció — minimális, maximális fokszám és izolált csúcs

• \(G\) gráf minimális fokszáma: \(\delta(G) = \min \{ d(v) \mid v \in V(G) \}\).
• \(G\) gráf maximális fokszáma: \(\Delta(G) = \max \{ d(v) \mid v \in V(G) \}\).
• Egy \(G\) gráfban egy csúcs izolált csúcs, ha fokszáma \(0\) (\(d(v) = 0\)).

Definíció — reguláris gráf

Legyen \(G\) gráf, \(k \in \mathbb{N} \cup \{0\}\). Ekkor \(G\) \(k\)-reguláris gráf, ha \(\forall v \in V(G) : d(v) = k\). Például az üres gráfok \(0\)-regulárisak, a körgráfok \(2\)-regulárisak.

Tétel — kézfogási tétel

Ha \(G\) gráf, akkor:

\[ \sum_{v \in V(G)} d(v) = 2 \cdot |E(G)| \]

(A fokszámösszeg az élek számának kétszerese.)

Bizonyítás

Minden él kétszer számít be a fokszámösszegbe (a 2 végpontjánál), és ez a hurokélekre is igaz.

Következmény

1. Egy gráfban a csúcsok fokszámösszege páros.
2. Egy gráfban a páratlan fokszámú csúcsok száma páros.

Tétel

Ha \(G\) egyszerű gráf és \(|V(G)| \ge 2\), akkor van benne legalább két csúcs, amiknek azonos a fokszáma.

Bizonyítás

Legyen \(n = |V(G)|\). Mivel \(G\) egyszerű, így a lehetséges fokszámok: \(0, 1, \dots, n-1\) (\(n\) féle). A \(0\) és \(n-1\) fokszám egyszerre nem fordulhat elő, hiszen az \(n-1\) fokú csúcs minden más csúccsal össze lenne kötve. Ezért egy gráfban legfeljebb \(n-1\) féle fokszám lehet. Mivel \(n\) db csúcs van, a skatulya-elv szerint van két azonos fokú csúcs.

Tétel

Legyen \(d_1, \dots, d_n \in \mathbb{N} \cup \{0\}\). Ekkor létezik gráf \(d_1, \dots, d_n\) fokú csúcsokkal \(\iff\) \(d_1 + \dots + d_n\) páros.

Bizonyítás

• ⟹: Lásd a kézfogási tétel következményét.
• ⟸: Ha \(d_1 + \dots + d_n\) páros \(\implies\) közöttük a páratlanok száma páros.
  • Ha \(d_i\) páros, \(d_i = 2k\) (\(k \in \mathbb{N} \cup \{0\}\)), akkor az \(i\)-edik csúcsra illesztünk \(k\) db hurokélt.
  • Ha \(d_j\) páratlan, \(d_j = 2l + 1\) (\(l \in \mathbb{N} \cup \{0\}\)), akkor a \(j\)-edik csúcsra illesztünk \(l\) db hurokélt, majd a páratlan számoknak megfelelő csúcsokat kettesével még összekötjük.

Tétel — Havel–Hakimi-tétel

Legyenek \(0 \le d_1 \le d_2 \le \dots \le d_n \le n-1\) egész számok. Ekkor létezik egyszerű gráf \(d_1, \dots, d_n\) fokú csúcsokkal pontosan akkor (\(\iff\)), ha létezik egyszerű gráf \(d_1, \dots, d_{n-d_n-1}, d_{n-d_n} - 1, \dots, d_{n-1} - 1\) fokú csúcsokkal.

Bizonyítás

⟹: Tegyük fel, hogy \(\exists G\) egyszerű gráf, hogy \(V(G) = \{v_1, \dots, v_n\}\) és \(d(v_i) = d_i\) (\(i=1, \dots, n\)).

Ha \(v_n\) szomszédai \(v_{n-1}, v_{n-2}, \dots, v_{n-d_n}\), akkor hagyjuk el \(v_n\) csúcsot és a belőle induló éleket. Így éppen a kívánt fokszámokkal rendelkező egyszerű gráfhoz jutunk.

Ha nem ez a helyzet, akkor olyan módosítást hajtunk végre a gráfon, hogy a fokszámok ne változzanak, de \(v_n\) 1-gyel több csúccsal legyen szomszédos \(v_{n-1}, \dots, v_{n-d_n}\) közül. Ezt többször alkalmazva előbb-utóbb a fenti már kezelt szituációhoz jutunk.

Módosítás lépései: most \(\exists i, j\), hogy \(1 \le i \le n - d_n - 1\) közötti, \(v_n\) és \(v_i\) szomszédos, és \(n - d_n \le j \le n-1\), \(v_n\) és \(v_j\) nem szomszédos. Feltétel alapján \(i < j \implies d_i \le d_j\).

1. Eset: ha \(d_i = d_j\), akkor \(v_i\) és \(v_j\) sorszámait felcserélve készen vagyunk.
2. Eset: ha \(d_i < d_j \implies d(v_i) < d(v_j) \implies\) van olyan csúcs \(v_k\), ami \(v_j\)-vel szomszédos, de \(v_i\)-vel nem. Ekkor hagyjuk el \((v_n, v_i)\) és \((v_j, v_k)\) közötti éleket, és vegyünk fel új éleket \((v_n, v_j)\) és \((v_i, v_k)\) közé. Ez megfelelő módosítás (mert \(v_n\) \(v_i\) helyett \(v_j\)-vel lett szomszédos), és nem változik a fokszám.

⟸: Tegyük fel, hogy létezik egyszerű gráf \(d_1, \dots, d_{n-d_n-1}, d_{n-d_n}-1, \dots, d_{n-1}-1\) fokú csúcsokkal. Vegyünk fel egy új csúcsot. Ezt kössük össze az utolsó \(d_n\) db számhoz tartozó csúcsokkal. Ekkor azok fokszáma 1-gyel nő, az új csúcs fokszáma \(d_n\) lesz.

Tétel

Legyen \(n \in \mathbb{N}, k \in \mathbb{N} \cup \{0\}\). Ekkor \(\exists\) \(n\) csúcsú \(k\)-reguláris egyszerű gráf \(\iff\) \(k \le n-1\) és \(n \cdot k\) páros.

Bizonyítás

⟹: Az egyszerűségből következik, hogy \(k \le n-1\). A kézfogási tétel miatt a fokszámösszeg \(= n \cdot k\) páros.

⟸:

1. Eset: ha \(k\) páros. Vegyünk fel egy körvonalon \(n\) db csúcsot és mindegyiket kössük össze balra \(\frac{k}{2}\) és jobbra \(\frac{k}{2}\) db csúccsal. A kapott gráf nyilván \(k\)-reguláris és egyszerű, mert a balra illetve jobbra vett \(\frac{k}{2}, \frac{k}{2}\) db csúcs közt nincs átfedés \(k \le n-1\) miatt.
2. Eset: ha \(k\) páratlan \(\implies n \cdot k\) páros \(\implies n\) páros. Vegyünk fel egy körvonalon \(n\) csúcsot és mindegyiket kössük össze balra \(\frac{k-1}{2}\), jobbra \(\frac{k-1}{2}\) csúccsal és az átellenes csúccsal (\(n\) páros). Ez \(k\)-reguláris és egyszerű.

Definíció — teljes gráf

Egy gráfot teljes gráfnak nevezünk, ha egyszerű és bármely két különböző csúcsa szomszédos. Jelölése: az \(n\) csúcsú teljes gráf \(K_n\).

Tétel

Egy \(n\) csúcsú teljes gráf éleinek száma:

\[ \frac{n(n-1)}{2} \]

Bizonyítás

1. bizonyítás: \(C_n^2 = \binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}\)

2. bizonyítás: az \(n\) csúcsú teljes gráfban minden csúcs fokszáma \(n-1\). Ekkor a fokszámösszeg \(n \cdot (n-1)\). A kézfogási tétel szerint: \(\frac{n(n-1)}{2} = \) élszám.

Definíció — komplementer gráf

Legyen \(G\) egyszerű gráf. Ekkor \(G\) komplementere az a \(\overline{G}\) egyszerű gráf, ahol \(V(\overline{G}) = V(G)\), és \(\overline{G}\)-ben két különálló csúcs pontosan akkor szomszédos, ha \(G\)-ben nem.

Definíció — él törlése

Legyen \(G = (V, E, \varphi)\) nemüres gráf és \(e \in E\). Ekkor az \(e\) él törlésével adódó gráf \(G - e = (V', E', \varphi')\), ahol:

\[ V' = V, \quad E' = E \setminus \{e\}, \quad \varphi' = \varphi|_{E'} \]

(a megmaradó élek végpontjai ugyanazok, mint \(G\)-ben voltak).

Definíció — csúcs törlése

Legyen \(G = (V, E, \varphi)\) gráf és \(v \in V\). Ekkor a \(v\) csúcs törlésével adódó gráf \(G - v = (V', E', \varphi')\), ahol:

\[ V' = V \setminus \{v\}, \quad E' = E \setminus \{ e \in E \mid v \in \varphi(e) \}, \quad \varphi' = \varphi|_{E'} \]

(\(v\) a végpontja \(e\)-nek).

Definíció — él összehúzása

Legyen \(G(V, E, \varphi)\) nemüres gráf, és \(e \in E\), hogy \(\varphi(e) = \{v, w\}\). Ekkor az \(e\) él összehúzásával adódó gráf \(G / e = (V', E', \varphi')\), ahol:

\[ V' = (V \setminus \{v, w\}) \cup \{x\} \quad (x \notin V \text{ az összeolvasztott pont}), \qquad E' = E \setminus \{e\}, \]

és \(f \in E'\) esetén:

\[ \varphi'(f) = \begin{cases} (\varphi(f) \setminus \{v, w\}) \cup \{x\}, & \text{ha } v \text{ vagy } w \in \varphi(f) \\ \varphi(f), & \text{ha } v, w \notin \varphi(f) \end{cases} \]