2.5 Reprezentace grafu

1 Úvod 2 Grafy 2.1 Grafy 2.2 Okolí a stupeň vrcholu 2.3 Sled, cesta a kružnice v grafu 2.4 Souvislost a izomorfismus 2.5 Reprezentace grafu 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 11 Dynamické programování Index Literatura

Definice 2.33

Nechť $G = (V, E)$ je graf s $V = {v_1, v_2, ..., v_n}$.Matice sousednosti grafu $G$ je čtvercová matice $A_G = (a_{ij})_{i,j=1}^{n}$ definovaná předpisem

\begin{equation*} a_{i,j} = \begin{cases} 1 & \text{když } {v_i, v_j} \in E \\ 0 & \text{jinak} \end{cases} \end{equation*}

Paměťová složitost: $O(n^2)$

Poznámka 2.6

Matice sousednosti $A_G$ je pro neorientované grafy symetrická matice.

Definice 2.34

Pro každý vrchol $v$ grafu $G = (V,E)$ uchováváme seznam jeho sousedů (např. spojový seznam)

Paměťová složitost: $O(n + m)$