• STOPNIEM WIERZCHOŁKA s (x) nazywa się liczbę gałęzi grafu incydentnych z wierzchołkiem x.

Wyraża się jako następującą sumę:

s(x) = s⁺(x) + s^-(x) + s^~(x) + s⁰(x)

przy czym:

• s⁺(x) liczba łuków „wychodzących” z wierzchołka x, nazywana stopniem zewnętrznym wierzchołka;

• s^-(x) - liczba łuków „wchodzących” do wierzchołka x, nazywana stopniem wewnętrznym wierzchołka;

• s^~(x) - liczba krawędzi incydentnych z wierzchołkiem x;

• s⁰(x) - liczba pętli incydentnych z wierzchołkiem x.

Na podstawie stopni wierzchołków definiuje się stopień grafu S(G) jako maksymalny stopień wierzchołka w tym grafie:

S(G) = max s(x)

x ∈ W

• MACIERZĄ PRZYLEGŁOŚCI WIERZCHOŁKÓW R (G) - nazywamy macierz symetryczną, której elementy określają liczbę gałęzi łączących odpowiednie pary wierzchołków grafu.

R(G) = [r_ij]_nxn' n=|W|

przy czym:

r_{ij =} |{u:<x_i,u,x_j> ∈P v <x_j,u,x_i> ∈P}|

gdzie:

• r_{ij -} jest liczbą gałęzi łączących wierzchołek x_i z x_j

• MACIERZĄ PRZYLEGŁOŚCI GAŁĘZI B(G) - nazywamy macierz postaci:

B(G) = [b_ij]_mxm' m=|U|

w której:

bij = {	1 - gdy gałęzie ui uj są przyległe, tzn. istnieje co najmniej jeden wierzchołek incydentny z tymi gałęziami lub gdy i = j
		0 - w przeciwnym razie.

• MACIERZĄ PRZEJŚĆ P(G) - nazywamy macierz postaci:

P(G) = [p_ij]_nxn', n=|W|

w której p_ij jest liczbą takich gałęzi u∈U, dla których <x_i, u, x_j> ∈ P,

przy czym:

p_ij = |{u:<x_i, u, x_j> ∈P}|

• KROTNOŚCIĄ GRAFU K(G) - nazwiemy liczbę

K(G) = max {k(x, y)}

<x, y> ∈ WxW

gdzie k(x, y) jest największą z następujących liczb: liczby krawędzi łączących wierzchołki x i y, liczby pętli incydentnych z każdym spośród x i y. Dla grafu na rys. 1.1 K(G) = 2

CHARAKTERYSTYKA WIERZCHOŁKÓW I GAŁĘZI