29) Связность, компоненты связности. Сильная и слабая связность. Выделение компонент сильной связности в орграфе.

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

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

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

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

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

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

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

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

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

30) Подграфы. Минимальный остов и алгоритм его построения.

Граф 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) ребер.

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

а) б) в) г) д)

31) Виды графов – пустой, полный, двудольный, сети.

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

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

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

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

С₃

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32) Операции над графами. Удаление и добавление вершин, ребер, стягивание вершин и подграфа, соединение, объединение и произведение графов.

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

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

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

1. Удаление вершины 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.

15. C₃ – v = K₂.

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

   

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

16. K₂ – e =K₂.

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

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

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

1. Стягивание подграфа А графа 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.

18. K₄ / C₃ =K₂.

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

2. Размножение вершины 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.

19. K₂v =C₃; C₃v =K₄ …

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

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

1. Соединением графов 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₂.

21. K_m,n.=K_m +K_n.

1. Произведением графов 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₂.

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

33) Деревья. Ориентированные деревья.

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

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

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

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

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

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

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

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

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

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

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

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

34) Способы представления графов в ЭВМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27. Списки смежности для заданных графа 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).

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

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

35) Понятие обхода графа. Поиск в глубину и в ширину

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36)Алгоритмы поиска кратчайших путей в графе. Алгоритм Дейкстры.

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

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

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

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

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 не станет постоянной вершиной, проделывать следующие шаги:

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

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

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

37) Алгоритмы поиска кратчайших путей в графе. Алгоритм Флойда-Уоршалла.

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

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

Идея: Строится специальная матрица 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.