Степен (теорија графова)

У теорији графова, степен чвора је број грана суседних том чвору. Степен чвора ${\displaystyle v}$ се означава са ${\displaystyle \deg(v)}$.

За неусмерен граф, степен чвора је број грана које су му суседне (инцидентне). Ово значи да се свака петља броји двапут. Ово је зато што свака грана има две крајње тачке, а свака крајња тачка додаје степен чвору.

Граф са десне стране има следеће степене:

У усмереном графу, свака грана има два различита краја: почетак, и крај (црта се као стрелица). Сваки крај се броји на различит начин. Број грана које улазе у неки чвор је улазни степен, а број грана које из чвора излазе је излазни степен .

Улазни степен се означава са ${\displaystyle \deg ^{+}(v)}$ а излазни степен са ${\displaystyle \deg ^{-}(v)}$

Граф са слике десно има следеће степене:

Ако чвор има степен нула, онда се он зове изолован чвор.

Ако чвор има степен 1, онда се он назива листом. Ово је уобичајено код стабала у теорији графова и код стабала као структура података.

Ако сваки чвор графа има исти степен, ${\displaystyle k}$ онда се граф назива k-регуларним графом и за сам граф се каже да има степен ${\displaystyle k}$.

Неусмерен граф је Ојлеров ако и само ако има или 0 или 2 чвора непарног степена. Ако је граф Ојлеров, могуће га је нацртати из једног потеза тако да се кроз сваку грану пролази тачно једном - ојлеров пут . Уколико је има 0 чворова непарног степена, тада цртање почиње и завршава се у истом (произвољном) чвору, а ако има 2 чвора непарног степена, тада цртање почиње у једном од њих, а завршава се у другом.

Формула суме степена тврди да ако је дат граф ${\displaystyle G=(V,E)}$,

${\displaystyle \sum _{v\in V}\deg(v)=2|E|,}$

јер је свака грана суседна са два чвора. Формула имплицира да у сваком графу број чворова непарног степена мора бити паран.