Gráfok mátrixai és irányított gráfok

Definíció — szomszédsági mátrix

Legyen \(G\) gráf és \(V(G) = \{v_1, \dots, v_n\}\). Ekkor \(G\) szomszédsági mátrixa az az \(A = (a_{ij})_{n \times n}\) mátrix, ahol \(a_{ij}\) a \(v_i, v_j\) csúcsok közötti élek száma (\(1 \le i, j \le n\)).

Tétel

Legyen \(G\) gráf, \(V(G) = \{v_1, \dots, v_n\}\), \(A\) a szomszédsági mátrixa és \(\ell \in \mathbb{N}\). Ekkor \((A^\ell)_{ij} =\) a \(v_i\)-ből \(v_j\)-be menő \(\ell\) hosszú séták száma.

Bizonyítás — \(\ell\) szerinti teljes indukcióval

\(\ell = 1\): ez az \(A\) mátrix definíciója.

Tegyük fel, hogy \(\ell\)-re igaz, ekkor \((\ell+1)\)-re:

\[ (A^{\ell+1})_{ij} = \sum_{k=1}^n (A^\ell)_{ik} \cdot a_{kj} \]

ahol \((A^\ell)_{ik}\) a \(v_i\)-ből \(v_k\)-ba menő \(\ell\) hosszú séták száma, \(a_{kj}\) pedig a \(v_k\)-ból \(v_j\)-be menő 1 hosszú séták (élek) száma. Ezek szorzata és összege megadja a \(v_i\)-ből \(v_j\)-be menő \(\ell+1\) hosszú séták számát.

Definíció — illeszkedési mátrix

Legyen \(G\) nem üres gráf, \(V(G) = \{v_1, \dots, v_n\}\) és \(E(G) = \{e_1, \dots, e_m\}\). Ekkor \(G\) illeszkedési mátrixa a \(B = (b_{ij})_{n \times m}\) mátrix, ahol:

\[ b_{ij} = \begin{cases} 1, & \text{ha } v_i \text{ és } e_j \text{ illeszkedik} \\ 0 & \text{amúgy} \end{cases} \]

(Nem hurokél oszlopában pontosan 2 db 1-es van, a végpontokhoz tartozó sorokban.)

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

Legyen \(V \ne \emptyset\) és \(E\) véges halmazok, valamint \(\Psi : E \to V \times V\) leképezés. Ekkor a \(D = (V, E, \Psi)\) hármast irányított gráfnak nevezzük. \(V\) elemei a \(D\) csúcsai, \(E\) elemei a \(D\) élei; ha \(e \in E\)-re \(\Psi(e) = (v, w)\), akkor az \(e\) él a \(v\) csúcsból a \(w\) csúcsba mutat (\(v\) az \(e\) él kezdőpontja, \(w\) a végpontja).

Definíció

Legyen \(D = (V, E, \Psi)\) irányított gráf:

• \(e \in E\) hurokél, ha \(\exists v \in V : \Psi(e) = (v, v)\).
• \(e, f \in E\) párhuzamos élek, ha \(\Psi(e) = \Psi(f)\) (itt számít az irány is!).

Definíció — egyszerű irányított gráf

Egy irányított gráf egyszerű, ha nincs benne hurokél és nincsenek benne párhuzamos élek.

Definíció — kifok és befok

Egy \(D\) irányított gráfban a \(v \in V(D)\) csúcs kifoka a \(v\)-ből kiinduló élek száma, befoka a \(v\)-be érkező élek száma. Jelölés: \(d_{\text{ki}}(v)\), \(d_{\text{be}}(v)\).

Definíció

Egy \(D\) irányított gráfban a \(v \in V(D)\) csúcs:

• izolált csúcs, ha \(d_{\text{be}}(v) = d_{\text{ki}}(v) = 0\)
• forrás, ha \(d_{\text{be}}(v) = 0\)
• nyelő, ha \(d_{\text{ki}}(v) = 0\)

Tétel — kézfogási tétel, irányított változat

Ha \(D\) irányított gráf, akkor:

\[ \sum_{v \in V(D)} d_{\text{ki}}(v) = |E(D)| = \sum_{v \in V(D)} d_{\text{be}}(v) \]

Bizonyítás

Minden élt egyszer számolunk mindkét összegben.

Definíció — irányított teljes gráf

Egy irányított gráfot irányított teljes gráfnak nevezünk, ha egyszerű, és bármely csúcsból bármely másik csúcsba vezet él.

Tétel

Egy \(n\) csúcsú irányított teljes gráf élszáma \(= n(n-1)\).

Bizonyítás

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

2. bizonyítás: minden csúcs kifoka \(= (n-1)\). Így a fokok összege (irányított kézfogási tétellel): \(n(n-1)\).

Definíció — irányított gráfhoz tartozó irányítatlan gráf, és irányítás

Legyen \(D = (V,E,\Psi)\) irányított gráf. A \(D\)-hez tartozó irányítatlan gráf \(G = (V,E,\varphi)\), ahol ha \(e \in E\)-re \(\Psi(e) = (v,w)\), akkor \(\varphi(e) = \{v,w\}\).

Megfordítva: legyen \(G = (V,E,\varphi)\) irányítatlan gráf. Ekkor \(G\) egy irányításán olyan \(D = (V,E,\Psi)\) irányított gráfot értünk, ahol ha \(e \in E\)-re \(\varphi(e) = \{v,w\}\), akkor \(\Psi(e) = (v,w)\) vagy \(\Psi(e) = (w,v)\).

Definíció — irányított séta, vonal, út, kör

Legyen \(D = (V,E,\Psi)\) irányított gráf. Ebben \((v_0, e_1, v_1, e_2, v_2, \dots, v_{\ell-1}, e_\ell, v_\ell)\) irányított séta, ha \(v_0, v_1, \dots, v_\ell \in V\), \(e_1, e_2, \dots, e_\ell \in E\), továbbá \(\Psi(e_i) = (v_{i-1}, v_i)\) minden \(i = 1, \dots, \ell\) esetén. A séta hossza az élek száma. A fentiekhez hasonlóan definiálható a nyílt/zárt irányított séta, irányított vonal, irányított út, irányított kör.

Definíció — erősen és gyengén összefüggő

Legyen \(D\) irányított gráf.

• \(D\) erősen összefüggő, ha minden csúcsból minden másik csúcsba vezet irányított út.
• \(D\) gyengén összefüggő, ha a \(D\)-hez tartozó irányítatlan gráf összefüggő.

Definíció — irányított Euler-vonal

A zárt / nyílt irányított Euler-vonal definíciója az irányítatlan esethez hasonló.

Tétel — Euler, zárt irányított változat

Legyen \(D\) izolált csúcsmentes irányított gráf. Ekkor \(D\)-ben van zárt irányított Euler-vonal \(\iff\) \(D\) gyengén összefüggő és \(\forall v \in V(D) : d_{\text{ki}}(v) = d_{\text{be}}(v)\).

Bizonyítás

⟹: nyilvánvaló.

⟸: az irányítatlan esethez hasonlóan készítsünk egy csúcsból kiindulva irányított vonalat, amíg el nem akadunk — ez zárt irányított vonal lesz. Ha van olyan él, amely nincs benne, az háromféle lehet:

• 1. típus: ha a kezdőpontja (\(v\)) a zárt irányított vonalban van — ekkor \(v\)-ből az adott élen indulva, az eredeti vonal éleit nem használva építünk egy új zárt irányított vonalat, amit \(v\)-nél beilleszthetünk az eredetibe.
• 2. típus: ha a végpontja (\(w\)) van a zárt irányított vonalban. Mivel \(d_{\text{ki}}(w) = d_{\text{be}}(w)\), van olyan él is a vonalon kívül, ami \(w\)-ből indul, azaz 1. típusú, ami már kezelve van.
• 3. típus: ha sem a kezdő-, sem a végpontja nincs a zárt irányított vonalban — a gyenge összefüggőség miatt ez 1. vagy 2. típusú él létezését eredményezi.

Tétel — Euler, nyílt irányított változat

Legyen \(D\) izolált csúcsmentes irányított gráf. Ekkor \(D\)-ben van nyílt irányított Euler-vonal \(\iff\) \(D\) gyengén összefüggő, és \(\exists x, y \in V(D)\):

\[ d_{\text{ki}}(x) = d_{\text{be}}(x) + 1, \quad d_{\text{be}}(y) = d_{\text{ki}}(y) + 1 \]

továbbá \(\forall v \in V(D) \setminus \{x, y\} : d_{\text{ki}}(v) = d_{\text{be}}(v)\).

Bizonyítás

⟹: nyilvánvaló (\(x\) a nyílt irányított Euler-vonal legelső csúcsa, \(y\) pedig az utolsó csúcs).

⟸: húzzunk be egy új élt \(y\)-ból \(x\)-be. Ezzel visszavezettük a zárt irányított változatra.

Definíció — irányított Hamilton-út, irányított Hamilton-kör

Irányított H-út, irányított H-kör definíciója értelemszerű.

Tétel

Legyen \(D\) egyszerű irányított gráf.

1. Ha \(D\)-ben van irányított H-kör \(\implies\) van irányított H-út.
2. Ha \(D\)-ben van irányított H-kör \(\implies D\) erősen összefüggő.
3. Ha \(D\)-ben van irányított H-út \(\implies D\) gyengén összefüggő.

Bizonyítás

(2)-nél mint az előbbi megjegyzésben zárt irányított Euler-vonal esetén. (3)-ban nem garantálható az erős összefüggőség (pl. egyetlen, egy irányba mutató él).

Tétel — Woodall–Ore, irányított változat

Legyen \(D\) egyszerű irányított gráf és \(|V(D)| \ge 3\). Tegyük fel, hogy \(v, w \in V(D)\) olyan csúcsok, hogy nincs él \(v\)-ből \(w\)-be. Ekkor ha \(d_{\text{ki}}(v) + d_{\text{be}}(w) \ge |V(D)|\), akkor \(D\)-ben van irányított Hamilton-kör.

Következmény — Nash-Williams–Dirac, irányított változat

Legyen \(D\) egyszerű irányított gráf és \(|V(D)| \ge 3\). Ha \(\forall v \in V(D) : d_{\text{ki}}(v) \ge \frac{|V(D)|}{2}\) és \(d_{\text{be}}(v) \ge \frac{|V(D)|}{2}\), akkor \(D\)-ben van irányított Hamilton-kör.

Tétel

Ha \(D\) irányított körmentes irányított gráf, akkor \(D\)-ben van forrás és nyelő.

Bizonyítás

Bizonyítsuk a nyelő létezését indirekt módon: tegyük fel, hogy nincs nyelő \(\implies\) minden csúcsból megy ki él. Induljunk el valamelyik csúcsból — mindig tovább tudunk menni. A végesség miatt előbb-utóbb lesz ismétlődés, így keletkezik egy irányított kör, ami ellentmondás. Forrásra hasonlóan bizonyítható, csak "visszafelé" lépkedünk a gráfban.

Tétel — topologikus sorrend

Legyen \(D\) irányított gráf. Ekkor \(D\) irányított körmentes \(\iff\) a csúcsoknak van olyan sorrendje, hogy minden él kezdőpontja előbb szerepel, mint a végpontja (topologikus sorrend).

Bizonyítás

⟹: irányított körmentes esetben az előző tétel szerint van forrás, legyen ez az 1. csúcs. Ezt törölve is van forrás, legyen ez a 2. csúcs, stb. Ez a sorrend topologikus sorrend: nem lenne az, ha \(\exists k, \ell : k \ge \ell\) és él megy a \(k\)-adik csúcsból az \(\ell\)-edik csúcsba — de akkor az \(\ell\)-edik lépésben választott csúcs nem lett volna forrás.

⟸: topologikus sorrend létezése esetén mindig csak nagyobb sorszámú csúcsba lehet lépni, így nem juthatunk vissza a kiinduló csúcsba \(\implies\) nincs is kör.

Tétel — Gallai, Roy

Legyen \(G\) egyszerű irányítatlan gráf. Ekkor \(G\) minden irányításában van \(\chi(G)-1\) hosszú irányított út.

Tétel — Stanley

Legyen \(G\) egyszerű irányítatlan gráf. Ekkor \(|P_G(-1)| = \) irányított körmentes irányítások száma.

Definíció — irányított szomszédsági mátrix

Legyen \(D\) irányított gráf és \(V(D) = \{v_1, \dots, v_n\}\). Ekkor \(D\) szomszédsági mátrixa \((a_{ij})_{n \times n}\), ahol \(a_{ij} = v_i\)-ből \(v_j\)-be menő élek száma (\(1 \le i, j \le n\)) — nem feltétlenül szimmetrikus mátrix.

Definíció — irányított illeszkedési mátrix

Legyen \(D\) irányított gráf, \(V(D) = \{v_1, \dots, v_n\}\) és \(E(D) = \{e_1, \dots, e_m\}\). Ekkor \(D\) illeszkedési mátrixa \((b_{ij})_{n \times m}\), ahol:

\[ b_{ij} = \begin{cases} -1, & \text{ha } v_i \text{ kezdőpontja } e_j\text{-nek, és } e_j \text{ nem hurokél} \\ 1, & \text{ha } v_i \text{ végpontja } e_j\text{-nek, és } e_j \text{ nem hurokél} \\ 0 & \text{amúgy} \end{cases} \]