Степінь вершини графа

Нехай G(V) - неорієнтований граф.

Визначення. Степенем r(a) деякої вершини a Î V називається кількість ребер графу, інцидентних цій вершині.

Якщо граф заданий матрицею суміжності вершин, то

(1)

Для матриці інцидентності аналогічна формула має вигляд

(2)

Число ребер у графі G позначимо через v_E = v_E(G). При підрахунку суми кожне ребро e(v_i, v_j), графу G підраховується двічі: один раз – як таке, що з’єднує вершину v_i з v_j, а другий раз – як таке, що з’єднує v_j з v_i. Тому

(3)

(формула (3) залишається правильною і для графу з петлями, якщо їх розглядати як подвійні ребра).

Оскільки в лівій частині формули (3) стоїть парне число, то це означає, що у скінченному графі без петель кількість вершин з непарним степенем – парна.

Визначення. Граф називається однорідним степеня k, якщо r(v_i = k), для всіх v_i Î V.

В однорідному графі кількість ребер згідно з формулою (3) v_E = nk/2.

Визначення. Повний граф U = U(V) - це неорієнтований граф, у якому дві довільні вершини з’єднані рівно одним ребром.

Зрозуміло, що повний граф U(V) з n вершинами – це однорідний граф степеня (n ‑ 1). Тому v_E = n(n – 1) / 2.

Визначення. Повний граф з петлями U₀ = U₀(V) - це повний граф, у якому до кожної вершини додана петля.

Кількість ребер у повному графі з петлями v_E(U₀) = v_E(U) + n = n(n + 1) / 2.

Нехай тепер G(V) - орієнтований граф. Тоді через r(v_i) і r*(v_i) позначають кількість ребер, які виходять з вершини v_i і входять в вершину v_i відповідно.

Аналогічно попередньому кількість ребер в орієнтованому графі

.