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

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

Неусмерени графови

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

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

чвор	степен
1	2
2	3
3	2
4	3
5	3
6	1

Усмерени графови

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

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

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

чвор	улазни степен	излазни степен
1	0	2
2	2	0
3	2	2
4	1	1

Специјални случајеви степена чворова

Изолован чвор

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

Лист

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

Регуларан граф

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

Ојлеров граф

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

Неке теореме

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

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

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