Graph (mathematics)

Graf G = (U, H), kde:

• U je konečná množina uzlů (vrcholů)
• H je konečná množina hran, H ⊆ {{u, v}¹⁾ | u, v ∈ U ∧ u ≠ v}

Ohodnocený graf má u hran přiřazenou jejich váhu.

Úplný graf je, když je každý uzel spojený s každým. |H| = n(n − 1) / 2.

Stupeň uzlu je počet hran které z něj vycázejí.

Suma stupňů všech uzlů je 2|H|²⁾.

Cesta je posloupnost P = (v₀, e₁, e₁, …, eₙ, vₙ) pro kterou platí eᵢ = {vᵢ₋₁, vᵢ}³⁾, vᵢ ≠ v_j, i ≠ j. Je to tedy posloupnost vrcholů, pro kterou platí, že v grafu existuje hrana z daného vrcholu do jeho následníka. Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují.

Kružnice je cesta která má počáteční a koncový uzel stejný.

Pokud cesta (nebo kružnice) prochází všemi vrcholy, je to Hamiltonská cesta (nebo kružnice).

Graf je souvislý, pokud mezi každými dvěma uzly existuje cesta. Prostě pokud se graf neskládá z izolovaných podgrafů, je souvislý.

Komponenta grafu je nějaký izolovaný podgraf. Pokud je graf souvislý, existuje právě jedna.

Most je ta hrana, kterou když odstraníme tak získáme dvě komponenty.

Strom je spojitý graf bez cyklů.