40 Обходы графов. Алгоритмы поиска в глубину и в ширину. Теорема о поиске в глубину и ширину.

Обх гр — это некоторое систематическое перечисление его вершин и/или ребер. Найболее практически важные обходы которые исп ин-фо о графе, например списки ребер(вершин), списки смежности. Различают обход графа в ширину, в глубину. Вид обхода определяется структурой данных, которые исп для хранения ин-фы о списках смежности. (стек — в глубину, очередь — в ширину)

Алгоритм обхода в глубину (в ширину).

Вход: Граф G={V,E} задан при помощи списка смежности.;

Выход: Последовательность вершин обхода.;

1)Помечаем все вершины как не пройдѐнные (Х[v] = 0);

2)Выбираем любую вершину графа которая будет корнем обхода, добавляем в структуру Т и помечаем эту вершину как пройдѐнную.

3)Извлекаем вершину u из Т и выдаѐм вершину u на выход алгоритма.

4)Для вершин принадлежащих списку см-ти, определяем все вершины смежные u,

5)Если они не помечены как пройдѐнные, заносим их в T и помечаем как пройдѐнные,

6)Если Т не пусто выполняем переходим к (3)

7)Если Т пусто завершаем работу алгоритма.

№41

Степенью вершины графа G называется число ребер инцидентных вершине.

Р(1) = 2, Р(2) = 3, Р(3) = 2, Р(4) = 3. (рис.1)

Обозначается степень вершины v графа G:  degGv или просто deg v,  если ясно, о каком графе G идет речь.

Граф, который имеет конечные степени вершин, называется локально-конечным. (рис.2)

Для того, чтобы посчитать степень вершины графа, заданного матрицей смежности или инцидентности, необходимо просуммировать элементы Eij. Если в графе существуют висячие вершины, их степень – 1. Если граф является пустым, то степени его вершин равны 0.

Граф называется однородным (регулярным), если степени всех его вершин равны. Обозначают:  , где k – степень каждой вершины графа, n – число вершин графа. Число, которому равны степени всех вершин, называется степенью данного однородного графа.

Последовательность степеней вершин графа G, записанная в каком либо порядке называется степенной последовательностью графа G. (2,3,2,3 – рис.1)

42.Операции с частями графа.

Пусть G=(N,U), D=(N,W).

Дополнение ⌐Н части Н графа G называется мн-во всех ребер графа G не принадлежащих части графа Н.

Объединением(суммой) графов G и D: GD наз. граф, представляющий собой объединение мн-в вершин и рёбер исх графов (NM,UW).

Пересечением графов G и D: GD наз. граф (NM,UW).

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

Произведением графов G и D: G*D наз. граф (NM,UWT), где T={(i,j): iN,jM,ij}.

//Операция удаления вершины i из G строится G’=(N\{i},T), где T мн-во тех и только тех рёбер графа G, к-е не инцедентны вершине i.

Операция удаления ребра (i,j). Из G строится G’=(N,U\{(i,j)}).

Операция стягивания вершин по ребру (i,j)U. Результатом будет граф G’, который получается из G след. образом удаляются вершины (i,j) вместе с инцедентными этим вершинам рёбрами, добавляется новая вершина k, к-я смежна тем и только тем вершинам, к-е смежны вершине i или j.