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

Из Википедије, слободне енциклопедије

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

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

Граф са 6 чворова и 7 грана

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

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

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

Усмерени графови[уреди]

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

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

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

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

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

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

Изолован чвор[уреди]

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

Лист[уреди]

Неусмерен граф са листовима 4, 5, 6, 7, 10, 11, и 12

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

Регуларан граф[уреди]

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

Ојлеров граф[уреди]

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

Неке теореме[уреди]

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

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

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