9957

150

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

диаметральной цепью.

Одна из диаметральных цепей графа на рис. 3.56 порождается множеством вершин {1,3,6,7,8,9}.

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

Метод поиска в ширину.

Метод поиска в ширину позволяет легко найти расстояние от данной вершины до других вершин графа, и значит, определить удалённость данной вершины. Применив его для всех вершин графа, получим удалённости всех вершин, зная которые, можно найти радиус, диаметр графа, а также центры и периферийные центры.

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

необходимых для работы алгоритма, используется очередь – упорядоченная последовательность элементов, в которой новые элементы добавляются в конец, а старые удаляются из начала.

Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной,

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

151

Алгоритм поиска в ширину

Шаг 1. Всем вершинам графа присваивается значение не посещенная.

Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста (рис. 3.57).

Рис. 3.57. Демонстрация алгоритма поиска в ширину

Пример 3.26. Для графа на рисунке 3.58 найдем радиус, диаметр графа, а

также центры и периферийные центры, используя метод поиска в ширину.

Рис.3.58.

Суть метода заключается в расстановке меток, которая осуществляется по следующему правилу. Предположим, нужно найти расстояние от вершины v1

до других вершин. Присвоим вершине v1 метку 0. Всем вершинам, смежным с v1, присвоим метку 1. Затем всем вершинам, смежным с вершинами имеющими метку 1 (которые ещё не имеют метки), присвоим метку 2 и т. д., пока все вершины не получат метки. Легко видеть, что метка вершины будет равна расстоянию от v1 до данной вершины, а наибольшая из меток равна удалённости вершины v1. Так, в рассматриваемом примере e( v1) = 4.

152

Метод позволяет так же находить кратчайшие цепи между вершинами.

Если, например, нужно найти кратчайшую цепь от v1 до v10 , то после расстановки меток двигаемся в обратном порядке от вершины v10 , переходя каждый раз к вершине с меньшей меткой (такая обязательно найдётся; если их несколько, то выбираем любую): v10 → v7 → v4 → v2 → v1. В результате, получаем кратчайшую цепь: ( v1, v2 , v4 , v7 , v10 ).

Подсчёты удалённостей остальных вершин приводят к следующим результатам: e( v2 )=3, e( v3 )=3, e( v4 )=3, e( v5 )=3, e( v6 )=3, e( v7 )=3, e( v8 )=3,

e( v9 )=4, e( v10 )=4.

Таким образом, для данного графа G имеем: r(G) = 3 ; diam(G) = 4 ;

вершины v1, v9 , v10 являются периферийными центрами, а все остальные вершины – центрами.

Метод поиска в глубину

Поиск в глубину – это рекурсивный алгоритм обхода вершин графа. Если метод поиска в ширину проводился симметрично (вершины графа просматривались по уровням), то данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Таким образом, основная идея поиска в глубину: когда возможные пути по ребрам, выходящим из вершин,

разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными).

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

(один из которых исследован полностью), ранее посещенный узел (вершина).

Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

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

153

При поиске в глубину посещается первая вершина, затем необходимо идти вдоль ребер графа, до попадания в тупик. Вершина графа является тупиком,

если все смежные с ней вершины уже посещены. После попадания в тупик

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

Алгоритм поиска в глубину

Шаг 1. Всем вершинам графа присваивается значение не посещенная.

Выбирается первая вершина и помечается как посещенная.

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

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные (рис. 3.59).

Рис. 3.59. Демонстрация алгоритма поиска в глубину

Пример. 3.27. Для неориентированного связного графа на рис. 3.60.

рассмотрим работу алгоритма поиска в глубину.

154

Рис. 3.60.

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

Пусть обход начнется с узла 1, тогда порядок последовательности просмотренных узлов будет следующим: 1 2 3 5 4. Если выполнение начать,

например, с узла 3, то порядок обхода окажется иным: 3 2 1 5 4.

Задачи

1. Дайте классификацию маршрутов в графе, приведенном на рисунке 3.61.

(1, 2, 3, 5, 2); (2, 3, 5, 4); (2, 3, 4, 5, 3, 2); (3, 4, 5, 3).

Рис. 3.61.

2.Найдите в графе (рис.3.62) циклы, содержащие: а) 4 ребра; б) 6 ребер; в) 5

ребер; г) 10 ребер.

Рис.3.62

3. Определите имеют ли контуры орграфы с матрицами смежности:

4. Нарисуйте все графы с указанными свойствами и значениями параметров

(в скобках указано число искомых графов):

1)графы с единственным циклом, 5 вершин (9);

2)графы с единственным циклом, 6 вершин, 5 ребер (8);

3)связные, не имеющие циклов длины 3, 5 вершин (6);

4)имеющие цикл длины 6, 5 вершин (6);

5)связные, 6 вершин, 6 ребер (13);

6)связные, 5 ребер (12);

7)две компоненты связности, 4 ребра (9);

8)без изолированных вершин, 4 ребра (11)

5.Изобразите три подграфа графа G (рис.3.63) так, чтобы они были связными

G:

Рис. 3.63.

6.Сколько компонент связности имеет граф G (рис.3.64)? Составьте для него матрицу смежности в блочно-диагональном виде (каждой компоненте связности должен соответствовать определенный блок).

Рис. 3.64.

7.а) Найдите все перешейки (мосты) и разделяющие вершины (шарниры) в

графе G (рис.3.65); б) Найдите радиус, диаметр и центр.

156

Рис. 3.65.

8. Найдите радиус, диаметр и центр графа на рисунке 3.66.

Рис. 3.66.

9. Найдите радиус, диаметр и центр графа, заданного матрицей смежности:

10.Постройте граф, центр которого: 1) состоит ровно из одной вершины;

2)состоит из трех вершин и не совпадает с множеством всех вершин;

3)состоит из двух вершин; 4) совпадает с множеством всех вершин.

11. В заданном ориентированном

графе G (рис.3.67) укажите номера

сильно связанных вершин.

Рис. 3.67.

157

12.Найдите минимальный разрез в следующих графах (рис. 3.68):

G:

H:

Рис.3.68

13.Определите, имеют ли контуры орграфы с матрицами смежности:

Выясните, являются ли эти орграфы слабо связными или сильно связными. Постройте эти графы и составьте для них матрицы достижимости.

14. Среди графов, изображенных на рис. 3.69, укажите сильно связный,

односторонне связный и несвязный графы. Найдите матрицы достижимости.

Рис. 3.69.

15.Для графов, изображенных на рис.3.70, определите наибольшую клику.

Рис. 3.70.

158

16. Докажите, что отношение достижимости является отношением эквивалентности.

17.Граф задан матрицей инцидентности. Определите, у какой вершины

полустепень захода равна трем

18. Задания к практической работе.

Дан неориентированный граф (данные по вариантам). Определите:

1)диаметр и радиус этого графа;

2)центры и периферийные вершины графа;

3)цикломатическое число данного графа.

159