Глава 3 Элементы теории графов (стр. 5 )

Очевидно, что в каждом столбце матрицы инцидентности только два элемента отличны от 0 (или один, если ребро является петлей), т. к. ребро может быть инцидентно не более чем двум вершинам (а столбец соответствует ребру). Поэтому матрица содержит много нулей и такой способ описания неэкономен. M(n, m)=O(n×m).

3) Списки смежности.

Граф представляется с помощью списочной структуры (списка смежности), отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин. Элемент списка представлен структурой с двумя полями: номер вершины и указатель. Для неориентированных графов M(n,m)=O(n+2m), для орграфов M(n,m)=O(n+m).

  Пример 3.28  Списки смежности для заданных графа G и орграфа D:

4) Массив ребер (дуг).

нач	кон	нач	кон
1	2	1	2
1	4	2	3
2	3	2	4
2	4	4	1
3	4	4	3

Отношение инцидентности можно задать также списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. M=O(2m).

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

По списку ребер графа легко построить матрицу инцидентности, т. к. каждое ребро этого списка соответствует столбцу матрицы, а номера вершин в каждом элементе списка – это номера строк матрицы инцидентности, элементы в которых равны 1. Для орграфа координата начала – номер строки, где стоит
–1, а координата конца – номер строки, где стоит 1.

3.4.3  Обходы графов

Обход графа – это некоторое систематическое перечисление его вершин (ребер). Среди всех обходов наиболее известны поиск в глубину и в ширину. Алгоритмы такого поиска лежат в основе многих алгоритмов на графах.

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

Поиск основывается на следующих действиях.

1. Сначала все вершины считаются неотмеченными.

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

3. Следующие действия выполняются в цикле до тех пор, пока структура Т не станет пустой:

–  из структуры данных Т выбирается вершина u;

–  она выдается в качестве очередной пройденной вершины;

–  перебираются все вершины из Г(u), и все те, которые не помечены, тоже заносятся в структуру Т и помечаются.

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

Теорема 3.3  Если граф G связен и конечен, то поиск в ширину или поиск в глубину обойдет все вершины графа по одному разу.

Доказательство. 1. Единственность обхода. Обходятся только вершины, попавшие в Т. Для помещения в Т выбирают только неотмеченные вершины; при попадании в Т вершина отмечается Þ " вершина будет обойдена по 1 разу.

2. Завершаемость алгоритма. Всего в Т может попасть не более m вершин; на " шаге одна вершина удаляется из Т Þ алгоритм stop не >, чем через m шагов.

3. Обход всех вершин. От противного. Предположим, что алгоритм закончил работу, а вершина w не обойдена. Значит, она не попала в Т и не была отмечена. Þ все вершины, смежные с ней, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены. Но граф G связен, значит, существует путь áv,wñ; значит, вершина v не отмечена. Но она была первой отмеченной вершиной! Противоречие.<

  Пример 3.30  Рассмотрим алгоритмы поиска в глубину и в ширину на примере. В качестве стартовой возьмем вершину с номером 3. Тогда поиск в ширину даст последовательность вершин: 3®T. T={3}Þ 3: {2,5,6,4}®T; T={2,5,6,4}Þ 2: {1}®T; T={5,6,4,1}Þ 5: {8,9}®T; T={6,4,1,8,9}Þ 6: {7}®T; T={4,1,8,9,7}. Окружения всех этих вершин уже отмечены Þ они будут выданы по порядку. Итак, выполнен обход всех вершин графа в следующем порядке: 3,2,5,6,4,1,8,9,7. При поиске в глубину начало такое же: 3®T. T={3} Þ 3: {2,5,6,4}®T; T={2,5,6,4}Þ 4: {7}®T; T={2,5,6,7}Þ 7: {9}®T; T={2,5,6,9} Þ 9: {8}®T; T={2,5,6,8}Þ 8: {1}®T; T={2,5,6,1}. Оставшиеся вершины выдаются по порядку. В итоге последовательность вершин: 3,4,7,9,8,1,6,5,2.

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

3.4.4  Контрольные вопросы

1.  Какие существуют способы представления графа в ЭВМ?

2.  Как отличаются размеры матриц смежности и инцидентности одного графа?

3.  Матрица смежности какого графа симметрична – простого или ориентированного?

4.  Чем отличаются матрицы смежности псевдографа и простого графа?

5.  Какова особенность матрицы инцидентности?

6.  Какой объем памяти требуется для представления графа при помощи массива ребер (дуг)?

7.  Как можно задать граф с помощью списков смежности?

8.  Что такое обход графа? Какие виды обходов Вы знаете?

9.  В чем различие между поиском в глубину и поиском в ширину?

10.  Что является условием окончания обхода графа при поиске в глубину (в ширину)?

11.  В каком графе поиск в ширину или поиск в глубину обойдет все вершины ровно по одному разу?

12.  Как получить разные каркасы графа, используя только поиск в ширину?

3.5  Алгоритмы на графах

3.5.1  Выделение компонент связности в орграфах

Компоненты сильной связности (КСС) орграфа G – это его максимальные сильно связные подграфы. Каждая вершина орграфа принадлежит только одной КСС. Если вершина не связана с другими, то считается, что она сама образует КСС. Орграф, который получается стягиванием в одну вершину каждой КСС, называется фактор-графом, или конденсацией орграфа G.

  Пример 3.31  Слева на рисунке орграф, справа – его фактор-граф. Овальными линиями показаны КСС, стянутые в одну вершину фактор-графа.

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

Теорема 3.4  Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяется однозначно.

3.5.2  Кратчайшие пути

Задача поиска кратчайшего пути (наиболее дешевого или короткого) «от пункта A до пункта В» имеет массу практических приложений и различные алгоритмы решения. Математическая постановка задачи имеет следующий вид.

Рассматривается взвешенный граф (орграф) G(V,E), ребрам (дугам) которого сопоставлены веса, обозначающие длину (или стоимость) пути из одного конца ребра в другой. Если из вершины vi нет ребра (дуги) в вершину vj, то вес ребра (vi,vj) считается равным ¥. Для ребер, являющихся петлями (диагональ матрицы смежности), их веса считаются равными 0. Все компоненты матрицы – веса ребер, соединяющих соответствующие вершины. Требуется определить кратчайший путь из одной вершины в другую.

Наиболее широко известны два алгоритма поиска кратчайших путей. Алгоритм Дейкстры находит кратчайшее расстояние от одной фиксированной вершины до другой и указывает сам путь, длина которого равна этому расстоянию. Алгоритм Флойда-Уоршалла позволяет найти кратчайшие расстояния между всеми парами вершин графа.

Алгоритм Дейкстры

Находит кратчайшее расстояние от вершины v1 до вершины vn

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

Каждой вершине vk ставится в соответствие упорядоченная пара (m,vr), где первая координата означает наименьшее на текущий момент расстояние от старта – v1 – до вершины vk, а вторая координата указывает на предыдущую вершину на этом пути. Первоначально все вершины помечены парами (¥,0) и имеют статус временных. Постепенно по мере нахождения кратчайшего пути часть вершин становятся постоянными. Алгоритм заканчивает работу, когда постоянной станет вершина vn.

Алгоритм состоит из следующих шагов:

1.  Начать в вершине v1(¥,0), заменить ее метку на v1(0,0) и сделать эту вершину постоянной.

2.  Пока vn не станет постоянной вершиной, проделывать следующие шаги:

a.  Если вершина vk(m,vr) стала постоянной, то для всех смежных с ней временных вершин vj вычислить m+d(vk,vj) и сравнить с текущим расстоянием, которым помечена вершина vj. Если полученная сумма меньше, то текущее расстояние заменить ею, а вторую координату заменить на vk.