Grafi

(Neusmerjen, enostaven) graf: urejen par $G = (V, E)$ :

$V$ … neprazna množica točk/vozlišč grafa $G$
$E$ … množica povezav - parov točk - grafa $G$

Primer: $V = {u, v, w, x, y}$ in $E = {{u, v}, {u, w}, {v, w}, {v, x}} = {uv, u w, v w, vx}$

flowchart LR
	U((u)) --- V((v))
	U --- W((w))
	W --- V
	V --- X((x))
	Y((y))

Stopnja točke $v \in V (G)$ - $d e g (v)$ : število povezav, ki imajo $v$ za krajišče

Izolirana točka: točka stopnje $0$
List grafa: točka stopnje $1$
Graf je d-regularen: vsa vozlišča $G$ so stopnje $d$
Kubični graf: 3-regularen graf

Lema o rokovanju: Graf $G$ ima $n$ točk in $m$ povezav. Tedaj velja:

i = 1 \sum n d e g (v_{i}) = 2 * m

V vsakem grafu je sodo mnogo točk lihe stopnje
$G$ je d-regulared graf z $n$ točkami in $m$ povezavami $⟹$ $n * d = 2 * m$

Izomorfnost grafov $G_{1}, G_{2}$ - $G_{1} ≅ G_{2}$ : obstaja preslikava $f : V (G_{1}) \to V (G_{2})$ , za katero velja:

$f$ je bijektivna
$uv \in E (G_{1}) ⟺ f (u) f (v) \in E (G_{2})$

Izomorfizem ohranja število točk, število povezav, stopnje točk, število trikotnikov,sosednost in nesosednost točk, …

Cikel $C_{n}$ :

$V (C_{n}) = {v_{1}, ..., v_{n}}$ in $∣ V (C_{n}) ∣ = n$
$E (C_{n}) = {v_{1} v_{2}, v_{2} v_{3}, ..., v_{n - 1} v_{n}, v_{n} v_{1}}$ in $∣ E (C_{n}) ∣ = n$
$d e g (v_{1}) = 2$ in $C_{n}$ je $2$ -regularen graf

Primeri: $C_{3} = K_{3}$ , $C_{4} = K_{2, 2}$
D-razsežna hiperkocka $Q_{d}$ : točke so zaporedja ničel in enic dolžine $d$ - dve točki/zaporedji sta sosedi, če se razlikujeta v natanko enem členu

$∣ V (Q_{d}) ∣ = 2^{d}$
$∣ E (Q_{d}) ∣ = d * 2^{d - 1}$
$Q_{d}$ je $d$ -regularen graf

Primeri: $Q_{0} = K_{1}$ , $Q_{1} = K_{2}$ , $Q_{2} = K_{4}$

Dvodelen/poln graf

Poln graf $K_{n}$ : vsaki njegovi točki sta sosedi

$V (K_{n}) = {v_{1}, ..., v_{n}}$ in $∣ V (K_{n}) ∣ = n$
$E (K_{n}) = {v_{i} v_{j}; 1 \leq i < j \leq n}$ in $∣ E (K_{n}) ∣ = \frac{n ( n - 1 )}{2}$
$d e g (v_{1}) = n - 1$ in $K_{n}$ je $(n - 1)$ -regularen graf

Dvodelen graf: točke grafa lahko pobarvamo z dvema barvama tako, da ima vsaka povezava krajišči različnih barv
Graf je dvodelen $⟺$ graf ne vsebuje ciklov lihe dolžine
Poln dvodelni graf na $n + m$ točkah: vsebuje dva barvna razreda z $n$ in $m$ točkami, pri čemer sta točki sosedi, če sta v različnih barvnih razredih

$V (K_{m, n}) = {v_{1}, ..., v_{m}, u_{1}, ..., u_{n}}$ in $∣ V (K_{m, n}) ∣ = m + n$
$E (K_{m, n}) = {v_{i} u_{j}; 1 \leq i \leq m \land 1 \leq j \leq n}$ in $∣ E (K_{m, n}) ∣ = m * n$
$d e g (v_{1}) = n$ , $d e g (u_{1}) = m$ in $K_{m, n}$ je $n$ -regularen graf

Primer: $K_{1, 1} = K_{2}$

Podgrafi

Podgraf $H$ grafa $G$ : iz originalnega grafa odstranjujemo točke in/ali povezave -

V (H) \subseteq V (G) E (H) \subseteq E (G)

Vpet podgraf: iz originalnega grafa odstranjujemo samo povezave -

V (H) = V (G)

Induciran podgraf: iz originalnega grafa odstranjujemo samo točke - skupaj s povezavami, ki se jih dotikajo - za vsako povezavo $e = uv \in E (G)$ velja

u, v \in V (G) ⟹ e = uv \in E (G)

Sprehodi v grafih

Sprehod $S$ v grafu $G = (V, E)$ : zaporedje točk $u_{0} u_{1} ... u_{n}$ , pri čemer sta zaporedni točki sprehoda sosedi na grafu $G$

začetek sprehoda: $u_{0}$
konec sprehoda: $u_{n}$

Dolžina sprehoda $S = u_{0} u_{1} ... u_{n}$ : $∣ S ∣ = n$

Razdalja med točkama $u$ in $v$ $D I ST (u, v)$ : dolžina najkrajše $u - v$ poti v grafu
u-v sprehod: sprehod z začetkom v $u$ in koncem v $v$
Graf je povezan, če za vsaki dve točki v grafu obstaja u-v sprehod

Tipi sprehodov:

Pot: nikoli ne gremo dvakrat čez isto točko - $u_{i} \neq = u_{j}$ za vse $0 \leq i < j \leq n$
Najkrajši $u$ - $v$ sprehod v grafu je pot
Obhod: začnemo in končamo v isti točki - $u_{0} = u_{n}$
Cikel: pot in obhod hkrati, prav tako mora veljati $n \geq 3$

Za sprehoda $S = u_{0} u_{1} ... u_{k}$ in $Z = u_{k} u_{k + 1} ... u_{l}$ je:

Obratni sprehod $S^{R} = S = u_{k} u_{k - 1} ... u_{0}$
Stik sprehodov $SZ = S = u_{0} u_{1} ... u_{k - 1} u_{k} u_{k + 1} ... u_{l}$
Odsek sprehoda $S_{u_{i} u_{j}} = u_{i} u_{i + 1} ... u_{j - 1} u_{j}$

Eulerjev graf

Enostaven sprehod: vsako povezavo uporabi največ enkrat
Eulerjev obhod: vsebuje vse povezave in vsa vozlišča
Eulerjev graf: (več možnih pogojev/opisov)

ima Eulerjev obhod
Eulerjev izrek: je povezan in vsa vozlišča so sodih stopenj
narišemo ga lahko samo z eno potezo, pri čemer je sklenjen

Prerezna točka: $G - v$ ima strogo več povezanih komponent kot $G$
Prerezna povezava: $G - e$ ima strogo več povezanih komponent kot $G$

$e$ je prerezna povezava $⟺$ $e$ ne leži na nobenem ciklu v grafu

Drevo/gozd

Gozd: graf brez ciklov
Drevo: povezan gozd
Naj bo $T$ drevo z $n$ točkami in $m$ povezavami:

$m = n - 1$
vsaka povezava v $T$ je prerezna
za poljubni točki $u, v$ obstaja natančno ena $u - v$ pot
če drevesu dodamo kakršnokoli novo povezavo, bo doljeni graf vseboval natanko en cikel

Vpeto drevo $H \subseteq G$ : $H$ je vpet podgraf v $G$ in $H$ je drevo

$G$ je povezan $⟺$ $G$ ima vsaj eno vpeto drevo
$T$ je drevo $\land$ $∣ V (T) ∣ \geq 2$ $⟹$ $T$ ima vsaj 2 lista
$G$ je povezan $\land$ $∣ V (G) ∣ \geq 2$ $⟹$ $G$ ima vsaj dve točki, ki nista prerezni

Hamiltonov graf

Hamiltonov cikel: cikel, ki:

gre skozi vsako točko grafa natanko enkrat in
gre skozi posamezno povezavo največ enkrat

Hamiltonov graf: ima Hamiltonov cikel

Dokaz, da graf je Hamiltonov: enostavno - poiščemo Hamiltonov cikel
Dokaz, da graf ni Hamiltonov: težavno - pregledati je potrebno vse cikle

Potrebni pogoji z razpadom grafa:

Povezan graf $G$ ni Hamiltonov, če vsebuje podmnožico točk:
$S \subseteq V (G)$ moči $∣ S ∣ = k$ , za katero velja, da ima $G - S$ vsa $k + 1$ povezanih komponent
Dvodelni graf $G$ ni Hamiltonov, če:
za njegova barvna razreda $V_{1}, V_{2}$ velja $∣ V_{1} ∣ \neq = ∣ V_{2} ∣$

Diracov zadostni pogoj:

Naj bosta $u, v$ nesosedi v grafu $G$ in naj zanju velja $d e g (u) + d e g (v) \geq ∣ V (G) ∣$ .
Potem velja: $G + uv$ je Hamiltonov graf $⟺$ $G$ je Hamiltonov graf
Naj bo $G$ graf z vsaj tremi točkami.
Potem velja: $\forall v \in V (G) : d e g (v) \geq \frac{n}{2} ⟹$ $G$ je Hamiltonov

Barvanje grafov

k-barvanje točk grafa $G$ : preslikava $c : V (G) \to {1, 2, ..., k}$ , pri kateri morata biti krajišči vsake povezave različnih barv - za vsako povezavo $uv \in E (G)$ tako velja $c (u) \neq = c (v)$
Kromatično število grafa $G$ $χ (G)$ : najmanjše $k \in N$ , za katerega obstaja $k$ -barvanje točk grafa $G$

$χ (G) \leq ∣ V (G) ∣$
$χ (G) \leq 1 ⟺$ $G$ je brez povezav
$χ (G) \leq 2 ⟺$ $G$ je dvodelen
$χ (K_{n}) = n, χ (\overline{K_{n}}) = 1, χ (K_{m, n}) = 2$
$T$ je drevo z vsaj dvema točkama $⟹ χ (t) = 2$
$n$ je sod $⟹ χ (C_{n}) = 2$ , $n$ je lih $⟹ χ (C_{n}) = 3$
$d \geq 1 ⟹ χ (Q_{d}) = 2$

SubNotes

Explorer