Теорема Эйлера (Лемма "о рукопожатиях"). Сумма степеней всех вершин графа является четным числом и равна удвоенному числу его ребер, т.е. . Для орграфа: .

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

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

Пример 3.6 Найдем степенную последовательность для графа G. Выпишем степени всех вершин графа в соответствии с их номерами (2,2,3,2,1).

3.2.2 Маршруты, цепи, циклы

Маршрутом от вершины u к вершине v или (u,v)-маршрутом в графе G называется всякая последовательность вида , в которой любые два соседних элемента инцидентны, т.е. e_k – ребро, соединяющее вершины v_k–1 и v_k, k = 1,2,…,n.

Ñ Это определение подходит также для псевдо-, мульти- и орграфов. В случае орграфа v_k–1 – начало ребра е_k , a v_k – его конец.

При этом вершину u называют началом маршрута, а вершину v – его концом. В маршруте некоторые вершины и ребра могут совпадать. Если u = v, то маршрут замкнут, а иначе открыт.

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

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

Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь – простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

Пример 3.7 (1,2,3,4,5,3,2) – маршрут, не являющийся цепью; (1,2,3,4,5,3) – цепь, не являющаяся простой; (1,2,3,4) – простая цепь; (1,2,3,4,5,3,1) – цикл, не являющийся простым; (1,2,3,1) – простой цикл.

Число ребер в маршруте M (возможно, с повторениями) называется его длиной, обозначается |M|.

Расстоянием между вершинами u и v (обозначается d(u,v)) называется длина кратчайшей цепи áu,vñ, а сама кратчайшая цепь называется геодезической.

Ñ Если не существует цепи, соединяющей вершины u и v, то по определению d(u,v) = +¥.

Диаметром графа G (обозначается D(G)) называется длина длиннейшей геодезической.

Максимальным удалением в графе G от вершины v называется r(v) = max d(v,v’), " v’ÎV. Вершина v графа G является его центром, если максимальное удаление от нее до всех вершин принимает наименьшее значение.

Множество вершин, находящихся на одинаковом расстоянии n от вершины v, называется ярусом (обозначается D(v,n)): D(v,n) = {uÎV | d(v,u) = n}.

Пример 3.8 Граф, любая из вершин которого является его центром – максимальное удаление до всех вершин от любой =1.

3.2.3 Связность

Если две вершины u и v в графе можно соединить цепью, то такие вершины связаны. Граф называется связным, если в нем связаны все вершины.

Легко видеть, что отношение связности на множестве вершин является отношением эквивалентности. Данное отношение разбивает множество вершин графа на классы, объединяющие вершины, связанные друг с другом. Такие классы называются компонентами связности; число компонент связности обозначается k(G).

Граф G является связным тогда и только тогда, когда он имеет одну компоненту связности: k(G) = 1. Если k(G) > 1, то это несвязный граф. Граф, состоящий только из изолированных вершин (в котором k(G)=|V|, r(G)=0), называется вполне несвязным.

Пример 3.9 Граф на рисунке имеет две компоненты связности.

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

Ориентированный граф G(V,E) является слабо связным (слабым), если симметричное замыкание множества E определяет связный граф (иными словами, если после замены всех дуг графа G ребрами полученный граф будет связным).

Ориентированный граф является сильно связным (сильным), если для любой пары вершин u,vÎV существует ориентированный путь из u в v (т.е. из любой вершины графа достижимы все его остальные вершины).

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

Ñ Множества вершин связных компонент образуют разбиение множества вершин графа.

3.2.4 Подграфы

Граф G’(V’,E’) называется подграфом графа G(V,E): G’(V’,E’) Í G(V,E), если V’Í V и E’Í E, и каждое из ребер E’ инцидентно только вершинам из V’.

Если G’Í G и множества вершин этих графов не равны, как и множества ребер, то подграф G’ является собственным подграфом графа G (Прим. 3.10, б).

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

Ñ Очевидно, что остов существует в каждом графе. Для его получения нужно удалить «лишние» ребра, разрушив циклы в каждой связной компоненте.

Остовный подграф для графа G можно построить не единственным образом. В общем, если (n,m)-граф G имеет k компонент связности, то для получения его остова из графа необходимо удалить (m–n+k) ребер.

Пример 3.10 (4,6)-граф G (а), его подграфы (б, в), причем б) – собственный подграф; 2 различных каркаса (г, д). Удаление ребер для получения остовного подграфа: (m–n+k) = 6 – 4 + 1 = 3. Þ из исходного графа требуется удалить 3 ребра (так, чтобы сохранились все вершины исходного графа и не стало циклов).

а) б) в) г) д)

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

1. Что такое степень вершины? Чем висячая вершина отличается от изолированной?

2. Какой граф называется регулярным?

3. Как связаны степень вершины и полустепень исхода, полустепень захода?

4. Что такое маршрут? Чем отличается замкнутый маршрут от открытого?

5. Какой маршрут называется цепью? Какая цепь является простой?

6. Чем цикл отличается от пути? А от контура?

7. Как определить длину маршрута? В чем она выражается?

8. Что такое расстояние между вершинами?

9. Что такое геодезическая? Как определяется диаметр графа?

10. Какой граф называется связным? Как называются классы эквивалентности вершин графа по отношению связности?

11. Может ли граф состоять из одних изолированных вершин и не иметь ребер? Сколько компонент связности имеет такой граф?

12. В чем различие между сильной и слабой связностью орграфа?

13. Что такое собственный подграф?

14. Какой подграф называется каркасом?

3.3 Виды графов и операции над ними

3.3.1 Тривиальные и полные графы

Наиболее простое строение имеют пустые и полные графы.

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

Граф, состоящий из простого цикла с k вершинами, обозначается C_k. Например, C₃ – треугольник, C₄ – квадрат.

Граф с n вершинами называется полным, если любые две его вершины смежны. Такой граф обозначается K_n, он имеет максимально возможное число ребер, равное n×(n–1)/2.

Пример 3.11

Ñ Очевидно, что в пустом графе все вершины изолированные, а в полном степень каждой вершины на 1 меньше порядка графа: deg(v)=n–1 "vÎV.

Полный направленный орграф называется турниром.

Утверждение:

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

Полный граф G(V,E) соответствует универсальному бинарномуотношению E на множестве вершин V (т.е. "u,vÎV (u,v)ÎE – любые два элемента (вершины) связаны этим отношением).

3.3.2 Двудольные графы

Двудольный граф (или биграф, или четный граф) – это граф G(V,E) такой, что множество вершин разбито на два непересекающихся подмножества V₁ и V₂: V₁ÈV₂=V, V₁ÇV₂=Æ так, что любое ребро соединяет вершину из V₁ с вершиной из V₂. Тогда множества V₁ и V₂ называются долями графа G.

Если граф содержит все ребра, соединяющие множества V₁ и V₂, то он называется полным двудольным графом. Если |V₁|=m и |V₂|=n, то полный двудольный граф обозначается K_m,n.

Пример 3.12 На рисунке показан полный двудольный граф K_3,3.

Теорема 3.2 Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Двудольные графы удобны для представления бинарных отношений между элементами двух разных типов, например: множества {исполнители} и {виды работ}. Тогда отношением E может быть «данный исполнитель может выполнять данную работу».

3.3.3 Плоский (планарный) граф

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

Говорят, что плоский граф допускает правильную укладку на плоскости.

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

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

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

Для любой плоской карты имеет место формула Эйлера: n – m + r = 2, где n – число вершин, m – число ребер, r – число областей карты (включая внешнюю область).

Пример 3.13 Полный двудольный граф K_3,3. и полный граф K₅ не являются плоскими.
Граф K₄ является планарным: см. рисунок. 1,2,3 – его внутренние грани, 4 – внешняя грань.

3.3.4 Направленные орграфы и сети

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

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

Пример 3.14 Граф на рисунке является сетью, вершина 1 – источником, а вершина 5 – стоком.

3.3.5 Операции над графами

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

1. Дополнением графа G₁(V₁,E₁) называется граф G₂(V₂,E₂), у которого множество вершин такое же, как у исходного графа, а множество ребер представляет собой дополнение до множества E₁: V₂=V₁, E=`E<sub>1</sub> =V<sub>1</sub>´V<sub>1</sub>\E<sub>1</sub>. Вершины графа G<sub>2</sub> смежны только в том случае, когда они не смежны в исходном графе. Обозначение: `G₁(V₁,E₁). Дополнение графов есть дополнение отношений.

Пример 3.15 Дополнение к полному графу – пустой граф. Другой пример показан на рисунке.

2. Удаление вершины v из графа G₁(V₁,E₁) (при условии vÎV₁): вершина v удаляется из множества V₁, а из множества ребер удаляются ребра, инцидентные этой вершине: V = V₁\{v}, E= E₁\{e = (v₁,v₂) | v₁ = v или v₂ = v}. Обозначение: G = G₁(V₁,E₁)–v.

Пример 3.16 C₃ – v = K₂.

3. Добавление вершины v в граф G₁(V₁,E₁) (при условии vÏV₁): во множество вершин добавляется вершина v: V = V₁È{v}, E = E₁. Обозначение: G = G₁(V₁,E₁) + v.

4. Удаление ребра e из графа G₁(V₁,E₁) (при условии eÎE₁): из множества ребер удаляется ребро e: V = V₁, E= E₁ \ {e}; его вершины сохраняются. Обозначение: G = G₁(V₁,E₁)–e.

Пример 3.17 K₂ – e =`K₂.

5. Добавление ребра e в граф G₁(V₁,E₁) (при условии eÏE₁): во множество ребер добавляется ребро e: V = V₁, E = E₁È{e}. Обозначение: G = G₁(V₁,E₁)+e.

6. Отождествление вершин v₁,v₂ графа G₁(V₁,E₁): замена этой пары новой вершиной v, причем все ребра, которые вели в удаленные вершины, заменяются ребрами, ведущими в v. Если эти вершины были смежными, то их отождествление называется стягиванием ребра.

Пример 3.18 (4,4)-граф после стягивания ребра превратился в K₂.

7. Стягивание подграфа А графа G₁(V₁,E₁) (при условии AÌV₁): из множества вершин удаляется множество A и заменяется новой вершиной v, все ребра, которые вели в вершины из А, заменяются ребрами, ведущими в v. V = V₁ \ A È {v}, E= E₁ \ {e = (u,v) | uÎA или vÎ A}È{e = (u,v) | uÎГ(A)\A}. Обозначение: G = G₁(V₁,E₁)/A.

Пример 3.19 K₄ / C₃ =K₂.

8. Подразбиение ребра графа G₁(V₁,E₁): удаление ребра и добавление новой вершины, которая соединяется ребром с каждой вершиной удаленного ребра.

9. Размножение вершины v графа G₁(V₁,E₁) (при условии vÎV₁, v’ÏV₁): во множество вершин добавляется вершина v’, во множество ребер – ребра, соединяющие новую вершину v’ с вершиной v и со всеми смежными с ней вершинами. V = V₁ È {v’}, E = E₁ È {(v,v’)} È {e = (u,v’) | uÎГ⁺(v)}. Обозначение: G = G₁(V₁,E₁)­v.

Пример 3.20 K₂­v =C₃; C₃­v =K₄ …

10. Объединением графов G₁(V₁,E₁) и G₂(V₂,E₂) (при условии, что их множества вершин, как и множества ребер, не пересекались) называется граф G(V,E), в котором V = V₁ÈV₂, E = E₁ÈE₂. Обозначение: G = G₁ÈG₂.

Пример 3.21 `K_3,3.= C₃ÈC₃. Любой граф является объединением своих компонент связности.

11. Соединением графов G₁(V₁,E₁) и G₂(V₂,E₂) (также при условии, что их множества вершин и множества ребер не пересекались) называется граф G(V,E), в котором V = V₁ÈV₂, E= E₁ÈE₂È{e=(v₁,v₂) | v₁Î V₁, v₂Î V₂}. Иными словами, строится объединение графов и добавляются ребра, соединяющие графы G₁(V₁,E₁) и G₂(V₂,E₂). Обозначение: G = G₁+G₂.

Пример 3.22 K_m,n.=`K<sub>m</sub> +`K_n.

12. Произведением графов G₁(V₁,E₁) и G₂(V₂,E₂) (также при условии, что их множества вершин и множества ребер не пересекались) называется граф G(V,E). В нем V = V₁×V₂, и вершины (u₁,u₂) и (v₁,v₂) смежны только в том случае, если либо u₁=v₁ и u₂ смежна с v₂, либо u₂=v₂ и u₁ смежна с v₁. Обозначение: G = G₁×G₂.

Пример 3.23

Операции над графами могут использоваться для построения графов с заданными свойствами.

3.3.6 Деревья

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

Дерево – это связный граф без циклов. Несколько деревьев (или несвязный граф без циклов) составляют лес. Таким образом, дерево является компонентой связности леса.

Свойства дерева:

1. Любые две вершины в дереве связаны единственной простой цепью.

2. При удалении любого ребра дерева нарушается его связность.

3. Число вершин в дереве на единицу больше числа ребер.

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

1. Существует единственный узел, у которого полустепень захода равна нулю – корень дерева.

2. Полустепень захода всех остальных узлов равна 1.

3. Каждый узел достижим из корня.

4. Узлы дерева с нулевой полустепенью исхода принято называть листьями.

Пример 3.24 Свободные (а) и ориентированные (б) деревья с 4 узлами.
а) б)

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

1. Какой граф является пустым? Чем он отличается от тривиального?

2. Что означает обозначение C₃? Чем этот граф отличается от K₃? А чем различаются C₄ и K₄?

3. Верно ли, что любой полный граф является регулярным?

4. Какой граф является двудольным? Чем отличается полный двудольный граф? Какой граф обозначается K_2,4.?

5. Дайте определение планарного графа.

6. Как определить число граней планарного графа?

7. Какой орграф является направленным графом?

8. Какой граф называется сетью?

9. Какой граф является дополнением к пустому графу?

10. Чем отличается удаление вершины от удаления ребра?

11. В чем различие операций стягивания ребра и отождествления вершин?

12. Чем отличается соединение графов от их объединения?

13. В каких деревьях существуют корень и листья?

14. Сколько существует различных неизоморфных деревьев с 5 вершинами?

3.4 Представление графов в ЭВМ

3.4.1 Требования к представлению графов

Чтобы задать граф, нужно каким-либо способом описать множество его вершин, множество его ребер, а также указать, какие вершины и ребра инцидентны (или смежны), т.е. задать отношение инцидентности (смежности).

Рассмотрим несколько способов представления графа в ЭВМ. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается по потребностям конкретной задачи.

Напоминание: число вершин графа обозначаем через n, а число ребер – через m. Характеристика M(n,m), приведенная для каждого представления, означает требуемый для него объем памяти.

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

Все представления будем иллюстрировать на конкретных примерах графа G и орграфа D (см. рисунок.).

3.4.2 Способы представления графа

1) Матрица смежности.

Матрица смежности A(G’) графа (орграфа) – это квадратная матрица размера n´n, у которой для любых i,j Î{1,2,…,n} элемент в i-й строке и j-м столбце равен 1, если i-я и j-я вершины соединены ребром (дугой с началом в вершине i), и равен 0 в противном случае.

Память M(n,m)=O(n²).

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

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

Пример 3.25 Матрицы смежности для заданных графа G и орграфа D

Ñ В матрице смежности мультиграфа или псевдографа число, находящееся на пересечении i-й строки и j-го столбца, совпадает с числом ребер, соединяющих вершины i и j, при этом каждая петля считается двумя ребрами.

Пример 3.26 Псевдограф, изображенный на рисунке, имеет матрицу смежности следующего вида:

2) Матрица инцидентности.

Другой способ задать граф – определить матрицу инцидентности (или инциденций) I(G), имеющую n строк и m столбцов, элементы которой задаются следующим образом:

Для ориентированного графа:

Пример 3.27 Матрицы инцидентности для заданных графа G и орграфа D

Очевидно, что в каждом столбце матрицы инцидентности только два элемента отличны от 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) Массив ребер (дуг).

нач	кон	нач	кон

Отношение инцидентности можно задать также списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. 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), ребрам (дугам) которого сопоставлены веса, обозначающие длину (или стоимость) пути из одного конца ребра в другой. Если из вершины v_i нет ребра (дуги) в вершину v_j, то вес ребра (v_i,v_j) считается равным ¥. Для ребер, являющихся петлями (диагональ матрицы смежности), их веса считаются равными 0. Все компоненты матрицы – веса ребер, соединяющих соответствующие вершины. Требуется определить кратчайший путь из одной вершины в другую.

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

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

Находит кратчайшее расстояние от вершины v₁ до вершины v_n

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

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

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

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

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

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

b. Найти минимум из расстояний, приписанных временным вершинам. Первую из таких вершин сделать постоянной.

3. Когда v_n станет постоянной вершиной, то расстояние, приписанное ей – это и есть длина кратчайшего пути. Сам путь (в обратном порядке) можно отследить, если пройти в обратную сторону – от вершины v_n к v₁ – по вторым координатам меток вершин.

Пример 3.32

F(¥,0)

Найти кратчайший путь из вершины А в вершину F во взвешенном графе. Вершины снабжаем пометками, и в графе будут присутствовать метки (¥,0), пока не найден путь. Вершины, которые будут становиться постоянными, выделяем жирным шрифтом.
а) б) в)
Вершина А стала постоянной (рис. а), с ней смежные В и С Þ для них нашли расстояния (это 5 и 6), заменили метки на (5,А) и (6,А). Минимальное из расстояний 5 Þ вершина В(5,А) становится постоянной (рис. б). Вычисляем расстояния от нее до смежных с ней С, Е, F, D. Расстояние до С будет 5+3=8 Þ оно больше текущего (6) Þ метка вершины С не меняется. Все остальные расстояния меньше ¥ Þ метки остальных вершин заменяются. Изо всех текущих меток расстояний min{12,15,7,6} = 6 Þ вершину С(6,А) делаем постоянной (рис. в). Смежная с ней временная вершина Е, расстояние до нее через С 6+7=13>7 Þ изменений нет. Теперь из временных вершин min=7 Þ вершина Е(7,В) становится постоянной. 7+4=11<15 Þ метка вершины F меняется на F(11,E) и она становится постоянной. Алгоритм завершен, расстояние от А до F равно 11, а кратчайший путь – A,B,E,F.

Алгоритм Флойда-Уоршалла

Находит кратчайшие расстояния между всеми парами вершин графа

Идея: Строится специальная матрица D, элементы которой – кратчайшие пути между всевозможными парами вершин графа G. При определении кратчайшего пути выбирается минимум из «прямого» расстояния между смежными вершинами v_i и v_j и суммарного расстояния при проходе через дополнительную вершину. Затем – более длинные пути и т.д.

Обозначим через длину кратчайшего пути из v_i в v_j с промежуточными вершинами во множестве {v₁,…,v_m}. Алгоритм использует три правила:

1) – вес дуги, соединяющий вершины v_i и v_j (т.е. первоначально матрица D – это исходная матрица весов).

2) .

3) Длина кратчайшего пути из вершины v_i в вершину v_j: .

Алгоритм строит матрицу за n шагов, т.е. строится матрица D⁽¹⁾, …, D⁽ⁿ⁾=D.

Пример 3.33

Найдем матрицу кратчайших расстояний для графа.
v₁ v₂ v₃

Элементы матрицы D⁽¹⁾ находим по правилу . Первая строка и первый столбец не меняются. Получаем . Элементы матрицы D⁽²⁾ находим по правилу . Без изменений второй столбец и вторая строка. .
Элементы матрицы D⁽³⁾ находим по правилу . . Каждый из элементов (i,j) матрицы D равен наименьшему расстоянию между вершинами v_i и v_j.

3.5.3 Минимальный остов

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

Для постановки и решения задачи дадим некоторые определения.

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

Математическая формулировка задачи: во взвешенном связном графе G(V,E) найти минимальное остовное дерево T(V,E’).

Рассмотрим алгоритм Краскала (Cruskal) решения этой задачи. Идея алгоритма состоит в том, чтобы постепенно формировать дерево Т(V,E’), выбирая ребра с наименьшим весом так, чтобы не возникало циклов.

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

1) Выбрать ребро минимального веса в исходном графе G, не принадлежащее множеству Е’, так, что его добавление в Е’ не создает цикла в дереве Т.

2) Добавить это ребро во множество ребер Е’.

Пример 3.34 Найти минимальный остов во взвешенном графе.
Построение остова начнем с ребра (v₁, v₃). Порядок присоединения ребер к остову:
(v₁, v₃), (v₂, v₅), (v₁, v₂) (или (v₁, v₅)), (v₄, v₅).
Вес остова W=1+2+1+4=8.

3.5.4 Эйлеровы графы

Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом. Эйлеровой цепью (или путем) является цепь (путь), которая включает все ребра (дуги) графа по одному разу. Собственная эйлерова цепь – это эйлерова цепь, которая не является эйлеровым циклом.

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