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).