01 Graf

Last updated Nov 9, 2022

• Neorientovaný graf je uspořádaná dvojice $(V, E)$, kde:
  • $V$ - neprázdná konečná množina vrcholů (Vertex)
  • $E$ - množina hran (Edge)
    • Hrana je 2-prvková podmnožina - neuspořádaná dvojice vrcholů ${u, v}$
    • Množinu všech možných hran (všech 2-prvkových podmnožin množiny $V$) označujeme $\binom{V}{2}$
• Obvykle graf označuje neorientovaný graf

• Množina vrcholů grafu $V(G)$
• Počet vrcholů $n = |V(G)|$

• Množina hran grafu $E(G)$

• Počet hran $m = |E(G)|$ ^21e7a3

• Nechť $e = {u, v}$, pak řekneme, že:

  • Vrcholy $u, v$ jsou koncové vrcholy hrany $e$
  • $u$ je sousedem $v$ a naopak
  • $u$ i $v$ jsou incidentní s hranou $e$ (incidence)

• Hrana je 2-prvková podmnožina $V$, platí tedy $E \subseteq \binom{V}{2} \subseteq 2^V$, např. pro $|V|=3$

  • $2^{V}= \mathcal{P}(V) = {\space {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} \space}$
  • $\binom{V}{2} = {\space {a,b}, {a,c}, {b,c} \space}$

• Sled délky $k$ je sekvence vrcholů a hran v grafu

• Značíme $P$
• Cesta je sled, ve kterém se neopakují vrcholy a tedy ani hrany
• Pro koncové vrcholy $s = v_0$ a $t = v_k$ mluvíme o s-t-cestě (připouštíme $s=t$, tedy může mít i 0 délku)
• Délka s-t-cesty $d(s,t)$ je počet hran v této cestě

$D[v]$ - pole vzdáleností $D$ $P[v]$ - pole předchůdců $P$