Stepen (teorija grafova)
U teoriji grafova, stepen čvora je broj grana susednih tom čvoru. Stepen čvora se označava sa .
Neusmereni grafovi
urediZa 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
urediU 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 a izlazni stepen sa
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
urediIzolovan čvor
urediAko čvor ima stepen nula, onda se on zove izolovan čvor.
List
urediAko č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
urediAko svaki čvor grafa ima isti stepen, onda se graf naziva k-regularnim grafom i za sam graf se kaže da ima stepen .
Ojlerov graf
urediNeusmeren 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
urediFormula sume stepena tvrdi da ako je dat graf ,
jer je svaka grana susedna sa dva čvora. Formula implicira da u svakom grafu broj čvorova neparnog stepena mora biti paran.