Co je graf
Proč grafy?
Skoro každá úloha v tomhle kurzu — nejkratší cesty, toky, obchodní cestující, rozvrhování s precedencemi — se formalizuje pomocí grafu (graph). Neformálně: graf se skládá z vrcholů (nodes, také uzly) a hran (edges); každá hrana spojuje dva vrcholy.
Hrana mezi vrcholy $v$ a $w$ může být dvojího druhu:
- Neorientovaná (undirected): symetrické spojení, zapisujeme jako množinu $e = \{v, w\}$.
- Orientovaná (directed): hrana z jednoho vrcholu vychází (leaves) a do druhého vstupuje (enters), zapisujeme jako uspořádanou dvojici $e = (v, w)$.
Zkus sám: jaký je praktický rozdíl mezi zápisem $\{v,w\}$ a $(v,w)$?
Množina $\{v,w\}$ nemá pořadí: $\{v,w\} = \{w,v\}$ — po neorientované hraně se dá „jít“ oběma směry. Uspořádaná dvojice $(v,w)$ pořadí má: $(v,w) \ne (w,v)$ — orientovaná hrana vede jen z $v$ do $w$. Proto se orientované hrany kreslí se šipkou.
Formální definice
Graf s vrcholy $V$ a hranami $E$ obvykle značíme $G = (V, E)$. Orientovaný graf (directed graph, digraph) má hrany — uspořádané dvojice $(v,w) \in V \times V$, $v \ne w$. Neorientovaný graf má hrany — dvouprvkové podmnožiny $\{v,w\} \subseteq V$. Obě množiny $V$ i $E$ jsou konečné.
Pár pojmů, které budeme potkávat pořád:
- Vrcholy $v$, $w$ hrany $e$ jsou její krajní vrcholy (endpoints); říkáme, že jsou s hranou incidentní (incident).
- Dvě hrany spojující tutéž dvojici vrcholů jsou paralelní hrany (parallel edges); graf s paralelními hranami je multigraf. Graf bez nich je prostý graf (simple graph) — s těmi pracujeme prakticky vždy.
- Podgraf (subgraph) $H$ grafu $G$ vznikne vynecháním některých vrcholů a/nebo hran (hrana v podgrafu musí mít oba krajní vrcholy).
- Úplný graf (complete graph) $K_n$: neorientovaný prostý graf na $n$ vrcholech, kde každá dvojice vrcholů je spojena hranou.
Zkus sám: kolik hran má úplný graf $K_5$?
Hrana = dvojice vrcholů, takže $\binom{5}{2} = 10$ hran. Obecně má $K_n$ přesně $\binom{n}{2} = \frac{n(n-1)}{2}$ hran. To je dobré číslo pro odhady: „hustý“ graf má až $O(n^2)$ hran.
Čísla na hranách: váha a kapacita
Samotná struktura grafu většinou nestačí — optimalizujeme přes čísla přiřazená hranám:
- Váha / cena (weight / cost) $c(e)$ — např. délka silnice. Minimalizujeme součet cen (nejkratší cesta, minimální kostra…).
- Kapacita (capacity) $u(e)$ — např. propustnost potrubí. Omezuje, kolik „toku“ smí hranou protéct (kapitola K4).
Neorientovaný graf jako digraf
Většina algoritmů v kurzu je formulovaná pro digrafy. Vadí to u neorientovaných grafů?
Zkus sám: jak z neorientovaného grafu vyrobit „ekvivalentní“ digraf?
Každou neorientovanou hranu $\{v,w\}$ nahradíme dvojicí protisměrných orientovaných hran $(v,w)$ a $(w,v)$ — obě se stejnou váhou/kapacitou. Po obou se dá jít „tam i zpět“, přesně jako po původní neorientované hraně. Proto stačí umět algoritmy pro digrafy.
Key takeaways — L0.1- Graf $G = (V, E)$: vrcholy + hrany; hrana spojuje dva vrcholy. Orientovaná hrana $(v,w)$ má směr (z $v$ do $w$), neorientovaná $\{v,w\}$ ne.
- Hrana může nést váhu/cenu $c(e)$ (minimalizujeme součet) a kapacitu $u(e)$ (omezuje tok).
- Neorientovanou hranu lze nahradit dvěma protisměrnými orientovanými hranami — algoritmy pro digrafy tak pokryjí i neorientované grafy.
- Prostý graf (simple) nemá paralelní hrany; úplný graf $K_n$ má $\binom{n}{2}$ hran.
“From an undirected graph we can make a digraph by replacing every undirected edge by a pair of inverse directed edges.” Apply this construction to the undirected graph drawn below (triangle $a, b, c$ with edge weights $c(\{a,b\})=2$, $c(\{b,c\})=5$, $c(\{a,c\})=4$): write down the node set $V$ and the edge set $E$ of the resulting digraph, including the weight of each directed edge.
a) Co je v zadání?
Máš neorientovaný trojúhelník se třemi váženými hranami. Úkol: přepsat ho na orientovaný graf (digraf) podle pravidla ze slidu — každá neorientovaná hrana → dvě protisměrné orientované — a vypsat $V$, $E$ i váhy.
b) Co k tomu budeme potřebovat?
- Jen tuhle lekci: zápis $\{v,w\}$ vs. $(v,w)$ a pravidlo náhrady.
c) Jak nad úlohou uvažovat?
Kolik orientovaných hran vznikne ze 3 neorientovaných? Jakou váhu dostane každá z dvojice protisměrných hran? (Stejnou jako původní hrana — jízda „tam“ stojí stejně jako „zpět“.)
d) Úplné řešení
Vrcholy se nemění: $V = \{a, b, c\}$. Každá ze 3 neorientovaných hran dá 2 orientované, celkem 6 hran:
$$E = \{(a,b), (b,a), (b,c), (c,b), (a,c), (c,a)\}$$Váhy: $c((a,b)) = c((b,a)) = 2$, $\;c((b,c)) = c((c,b)) = 5$, $\;c((a,c)) = c((c,a)) = 4$. Obecně: neorientovaný graf s $m$ hranami → digraf s $2m$ hranami, váhy se kopírují na obě protisměrné hrany.