Stopnja grafa

Lema o rokovanju pravi, da je za graf ${\displaystyle G(V,E)\,}$  dvojno število povezav enako vsoti vseh stopenj točk v grafu. To se zapiše kot:

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

kjer je:

• ${\displaystyle \deg(v)\,}$  stopnja točke ${\displaystyle v\,}$ 
• ${\displaystyle |E|\,}$  število povezav v grafu.

V neusmerjenih grafih je stopnja ${\displaystyle \deg \,}$  v grafih brez večkratnih povezav enaka številu sosedov točk, v grafih, ki vsebujejo večkratne povezave, pa je v vsaki točki enaka vsoti števila večkratnih povezav, ki so povezane s točko (so incidentne s točko).

 

V usmerjenem grafu ima vsaka povezava začetek in konec. Zaradi tega se lahko za vsako točko določi vhodno stopnjo (oznaka ${\displaystyle \deg ^{-}(x)\,}$ ) in izhodno stopnjo (oznaka ${\displaystyle \deg ^{+}(x)\,}$ ). Če se obravnava graf z večkratnimi povezavami, je:

• vhodna stopnja ${\displaystyle \deg ^{-}(x)\,}$  v grafih brez večkratnih povezav enaka številu sosednjih vozlišč.
• v grafih z večkratnimi povezavami v vsaki točki vhodna stopnja enaka vsoti števila vseh vstopajočih povezav.
• izhodna stopnja v grafih brez večkratnih povezav enaka številu sosednjih točk.
• izhodna stopnja v grafih z večkratnimi povezavami v vsaki točki enaka vsoti števila vseh izstopajočih povezav.

 

• točka, ki ima stopnjo enako 0, se imenuje izolirana točka.
• točka, ki ima stopnjo 1, se imenuje list

• če ima vsaka točka grafa enako stopnjo, je graf k-regularen. V tem primeru ima graf stopnjo k.
• usmerjeni graf je psevdogozd, če in samo če ima vsaka točka izhodno stopnjo največ 1. Funkcionalno je graf posebni primer psevdogozda, če ima vsaka točka izhodno stopnjo 1.
• neusmerjeni povezani graf ima Eulerjevo pot, če in samo, če ima 0 ali 2 točki s liho stopnjo. Kadar nima vozlišč z liho stopnjo je Eulerjeva pot Eulerjev krog.
• po Brooksovem izreku je v vsakem povezanem neusmerjenem grafu z največjo stopnjo ${\displaystyle \delta \,}$  kromatično število grafa največ enako ${\displaystyle \delta \,}$ , razen, če je graf klika ali sodi cikel, v tem primeru pa je kromatično število enako ${\displaystyle \delta +1\,}$ .
• po Vizingovem izreku ima vsak graf kromatično število enako ${\displaystyle \delta +1\,}$ .
• k-izrojen je graf v katerem ima vsak podgraf točko s stopnjo največ ${\displaystyle k\,}$ .

• Osnove teorije grafov Arhivirano 2005-12-11 na Wayback Machine. (slovensko)
• Uvod v teorijo grafov (slovensko)
• Stopnja (teorija grafov) – video (angleško)