2. Смежность, инцидентность, степени вершин.

Если х = {v, w} – ребро графа, то v, w называются концами ребра х, в этом случае говорят, что ребро х соединяет вершины v и w.

Если вершина v является концом ребра х, то говорят, что v и х инцидентны .

Вершины v, w графа G(V,X) называются смежными, если {v, w}Х.

Два ребра называются смежными, если они имеют общую вершину.

Рассмотрим граф на рисунке 13.1.

Вершине v₃ инцидентны ребра {v₃, v₃}, {v₃, v₁}, {v₃, v₂}, {v₃, v₄}.

Ребру {v₂, v₆} инцидентны вершины v₂, v₆.

Вершины v₅, v₆ – смежные, т.к. {v₅, v₆}- ребро. Вершины v₅, v₃ – не смежные, т.к. нет ребра их соединяющего.

Ребра {v₃, v₁}, {v₃, v₂}- смежные, т.к. имеют общую вершину v₃.

Степень вершины v – это количество ребер графа, инцидентных этой вершине. Обозначение  (v).

Для графа 13.1:

 (v₁) = 1  (v₅) = 2

 (v₂) = 2  (v₆) = 3

 (v₃) = 5  (v₇) = 0

 (v₄) = 1

Заметим, что вклад каждой петли равен двум.

Если степень вершины равна единице, то такая вершина называется висячей.

Если степень вершины равна нулю, то такая вершина называется изолированной.

Значит, вершины v₁ и v₄ – висячие, а вершина v₇ – изолированная.

Теорема о сумме степеней вершин графа: Для любого псевдографа G(V, X) выполняется равенство:

m – количество ребер графа. Действительно, каждое ребро графа инцидентно двум вершинам.

Проверим справедливость теоремы для графа 13.1:

m =7, 7 2 =14 и 1+2+5+1+2+3+0 =14.