Обходы графа

Обходы графа совершаются с целью поиска вершины или ребра (дуги), обладающей тем или иным признаком. По организации обхода вершин (ребер) различают

- поиск в ширину,

- поиск в глубину.

Для пояснения различий этих поисков по исходному графу построим дерево рис. 2.26 с корнем в вершине – начале обхода (это этаж 1), от этой вершины проводим ребра, инцидентные ей, получаем этаж 2. Затем аналогично строим следующий этаж и т.д.

Обход в ширину идет просмотром вершин этажа и далее по этажам. Это обслуживание очереди.

Обход в глубину – идем по ветви до конца, если нужная вершина не найдена, то возвращаемся до первого разветвления и далее по новой веточке вниз – обслуживание стека.

Рисунок 2.26

В псевдографе число ребер и дуг (петли либо не учитывают, либо учитывают как два ребра или дуги), инцидентных некоторой вершине х_i, называют степенью вершины (обозначение deg x_i).

Например, у графа показанного на рис. 2.27

степень вершины: x ₁: 6

(ребра е ₁, е ₂, е ₅, е ₇, е ₈, дуга е ₃);

степень вершины x ₂: 5

(ребра е ₁, е ₂, дуги е ₃, e ₄, e ₆);

степень вершины x ₃: 2

(ребро e ₅, дуга e ₄,);

степень вершины x ₄: 6

(ребра е ₇, е₈, e ₉, дуги e ₆, e ₁₀, e ₁₁);

степень вершины x ₅: 3

(ребро e ₉, дуга e ₁₀, дуга e ₁₁).

Рисунок 2.27

В неорграфе степень вершины равна числу инцидентных ей ребер, а сумма степеней вершин равна удвоенному числу его ребер:

Пример, подтверждающий справедливость этой формулы, показан на рис. 2.28.

Рисунок 2.28

Если deg v_i = 0, то эта вершина изолированная.

Если deg v_i = 1, то эта вершина висячая.

Для орграфа вводятся понятия полустепени исхода (deg⁺) и полустепени захода (deg^–) вершины, что соответствует числу выходящих и входящих дуг соответственно.

Для орграфа, показанного на рис. 2.29,

Рисунок 2.29

полустепень исхода вершины a: 2 (две выходящие дуги: 1, 2),

полустепень захода вершины a: 1 (одна заходящая дуга 10),

полустепень исхода вершины b: 1,

полустепень захода вершины b: 2

полустепень исхода вершины c: 2,

полустепень захода вершины c: 0,

полустепень исхода вершины d: 0,

полустепень захода вершины d: 2,

полустепень исхода вершины e: 1,

полустепень захода вершины e: 3,

полустепень исхода вершины f: 3,

полустепень захода вершины f: 0,

полустепень исхода вершины g: 1,

полустепень захода вершины g: 2.

Для орграфа и .

Если deg^– v_i = 0, то эта вершина – источник.

Если deg⁺ v_i = 0, то эта вершина тупиковая – сток.

Если граф имеет вершины одинаковой степени (полустепени исхода и захода), то его называют регулярным.

Вершины графа G (3,6) x ₁, x ₂, x ₃ (рис. 2.30) имеют одинаковую степень, равную 4, следовательно, G – регулярный граф.

Регулярный граф, в котором каждая пара смежных вершин имеет одинаковое число общих соседей и каждая пара несмежных вершин имеет свое одинаковое число общих соседей, называют сильно регулярным графом.

У графа, показанного на рис. 2.31, имеем

Смежные вершины Несмежные вершины

x ₁ и x ₂: 2 общих соседа: x ₄ и x ₃ х ₁ и х ₃: 2 общих соседа: x ₂ и x ₄