Stupeň vrcholu

Definice

Počet incidentních hran vrcholu $V$. Vrchol je izolovaný, pokud $degG(v) = 0$;

Značení

Označení pro počet hran obsahující vrchol V.
$deg_G(v)$, $d_G(v)$

Neorientovaný graf

Stupeň

$deg(v) =∣ \{ \{x, y\} ∈ E; x=v \} ∣.$^1

Orientovaný graf

Vstupní stupeň (incoming degree)

$deg^+(v) = ∣\{ (x, y) ∈ E; x=v \}∣$

Pokud deg⁺(v) = 0, pak nazýváme vrchol zdroj.

Výstupní stupeň (outgoing degree)

$deg^-(v) = ∣\{ (x, y) ∈ E; y=v \}∣$

Pokud $deg^-_G(v) = 0$, pak nazýváme vrchol stok.

Stupeň (degree)

Stupeň jako $deg(v) = deg^-(v) + deg^+(v)$.