Stepen (teorija grafova)

U teoriji grafova, stepen čvora je broj grana susednih tom čvoru. Stepen čvora $v$ se označava sa $\deg(v)$ .

Neusmereni grafovi

Za neusmeren graf, stepen čvora je broj grana koje su mu susedne (incidentne). Ovo znači da se svaka petlja broji dvaput. Ovo je zato što svaka grana ima dve krajnje tačke, a svaka krajnja tačka dodaje stepen čvoru.

Graf sa desne strane ima sledeće stepene:

čvor	stepen
1	2
2	3
3	2
4	3
5	3
6	1

Usmereni grafovi

U usmerenom grafu, svaka grana ima dva različita kraja: početak, i kraj (crta se kao strelica). Svaki kraj se broji na različit način. Broj grana koje ulaze u neki čvor je ulazni stepen, a broj grana koje iz čvora izlaze je izlazni stepen .

Ulazni stepen se označava sa $\deg ^{+}(v)$ a izlazni stepen sa $\deg ^{-}(v)$

Graf sa slike desno ima sledeće stepene:

čvor	ulazni stepen	izlazni stepen
1	0	2
2	2	0
3	2	2
4	1	1

Specijalni slučajevi stepena čvorova

Izolovan čvor

Ako čvor ima stepen nula, onda se on zove izolovan čvor.

List

Ako čvor ima stepen 1, onda se on naziva listom. Ovo je uobičajeno kod stabala u teoriji grafova i kod stabala kao struktura podataka.

Regularan graf

Ako svaki čvor grafa ima isti stepen, $k$ onda se graf naziva k-regularnim grafom i za sam graf se kaže da ima stepen $k$ .

Ojlerov graf

Neusmeren graf je Ojlerov ako i samo ako ima ili 0 ili 2 čvora neparnog stepena. Ako je graf Ojlerov, moguće ga je nacrtati iz jednog poteza tako da se kroz svaku granu prolazi tačno jednom - ojlerov put . Ukoliko je ima 0 čvorova neparnog stepena, tada crtanje počinje i završava se u istom (proizvoljnom) čvoru, a ako ima 2 čvora neparnog stepena, tada crtanje počinje u jednom od njih, a završava se u drugom.

Neke teoreme

Formula sume stepena tvrdi da ako je dat graf $G=(V,E)$ ,

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

jer je svaka grana susedna sa dva čvora. Formula implicira da u svakom grafu broj čvorova neparnog stepena mora biti paran.