Глава III. ТЕОРИЯ ГРАФОВ Граф – диаграмма связей между объектами. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Многие. - презентация

1 Глава III. ТЕОРИЯ ГРАФОВ Граф – диаграмма связей между объектами. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. 1. Основные понятия теории графов

2 В химии (для описания структур, путей сложных реакций) В информатике и программировании В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете. В экономике В логистике Применение теории графов: Пример. Существующие или вновь проектируемые сооружения рассматриваются как вершины, а соединяющие их дороги как рёбра. Применение различных вычислений, на таком графе, позволяет, например, найти кратчайший объездной путь или спланировать оптимальный маршрут.

3 Граф это совокупность непустого множества вершин и множества ребер, содиняющих пары этих вершин. Обозначим: Множество вершин: V = { v 1, v 2, …, v n } Множество ребер (дуг): E = { e 1, e 2, ….., e m } Граф - это упорядоченная пара G = G(V, E), где V - непустое множество вершин, элементы множества E – пары вершин: e k = ( v s, v t ), где s, t { 1, …, n } k { 1, …, т }

4 Графы ориентированные неориентированные a b c d e a b c d e G 1 - ориентированный граф G 2 - неориентированный граф Ориентированный граф – все ребра ( v s, v t ) являются упорядоченными парами вершин, т.е. для каждого ребра ( v s, v t ) определено направление из вершины v s в вершину v t. Неориентированный граф – все ребра ( v s, v t ) являются неупорядоченными парами вершин, т.е. ( v s, v t ) = ( v t, v s ) и возможно прохождение из вершины в вершину в обоих направлениях.

5 a b c d e a b c d e G 3 - ориентированный псевдограф G 4 - неориентированный псевдограф петля Направленный граф является одной из форм представления отношений и рассмотрен в теории множеств. кратные ребра Мультиграф граф, в котором существует пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений. Псевдограф мультиграф, допускающий наличие петель.

6 a b c d e G 5 – пустой граф – не содержит ни одного ребра, Е =. a b c d e G 6 = K 5 полный граф на 5-ти вершинах = каждые две различные вершины графа соединены одним и только одним ребром Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром.

7 a b c d e G 7 – цикл C 5 a b c d e G 8 – колесо W 5 f Деревья a b c d e f a b c d e f

8 Степени вершин Обозначим: G(v i ) = { v k | ( v i, v k ) E} - множество ребер которые выходят из вершины v i. G -1 (v i ) = { v k | ( v k, v i ) E} - множество ребер которые входят в вершину v i. Для ориентированного графа: Входящая степень вершины v i = количество ребер которые входят в вершину v i d t (v i ) = |G -1 (v i )| Исходящая степень вершины v i = количество ребер которые выходят из вершины v i d o (v i ) = |G(v i )|

9 Для неориентированного графа: G(v i ) = G -1 (v i ). Степенью вершины v i неориентированного графа называют количество рёбер, которым принадлежит эта вершина d(v i ) = d o (v i ) = d t (v i ). d o (v i ) = d t (v i ) = m, Свойство 1. В ориентированном графе: Свойство 2. где т = |Е| = числу ребер. В неориентированном графе: d (v i ) = 2m, где т = |Е| = числу ребер. При вычислении степени вершины петлю учитывают 2 раза.

10 Ребра 1 и 2 смежные, если они имеют общую вершину: Вершину a и ребро 1 назыывают инцидентными, если вершина a принадлежит ребру 1 : 1 2 a 1 a Вершины графа a и b называют смежными, если существует соединяющее их ребро: a b

11 Вершина называется изолированной, если она не является концом ни для одного ребра: Вершина называется висячей, если она является концом ровно одного ребра: a b c d e a b c d e изолированная вершина dеg( d ) = 0 висячая вершина dеg( d ) = 1

12 Матричное представление графов Матрица смежности K – квадратная матрица порядка n, строки и столбцы которой соответствуют вершинам графа, а элементы определяют число выходящих ребер. Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной. Для мультиграфа K ij 1. 1, если существует ребро из вершины i в вершину j, 0, иначе. K ij =

13 Матрица инцидентности I - строки которой соответствуют вершинам графа, столбцы – ребрам графа, а элементы определяют выходит ребро из вершины или входит в нее. 1, ребро выходит из вершины, -1, ребро входит в вершину, 0, ребро отсутствует или является петлёй. I ij = a b c d e

14 Изоморфизм графов a b c d e Два графа G 1 и G 2 называются изоморфными, если они имеют равное число вершин и равное число ребер, и существует взаимно однозначное соответствие между множествами их вершин, и множествами их ребер такое, что в графах соответствующие ребра соединяют соответствующие вершины. a b cd e

15 Маршрут. Связность графов Маршрутом, проходящим вершины v i, i = 1,..., k, называется последовательность ребер (v i,v i+1 ), i = 1,..., k-1 такая, что два соседних ребра имеют общую вершину. В случае ориентированного графа - ориентированный маршрут. Маршрут называется замкнутым, если его первая и последняя вершины совпадают. Длиной маршрута называют число составляющих его рёбер.

16 Маршрут называется цепью, если все его рёбра различны. Маршрут называется простой цепью, если все его рёбра и все вершины различны (кроме, может быть, начальной и конечной вершин). Замкнутая простая цепь называется циклом. Всякий маршрут, соединяющий две вершины, содержит простую цепь, соединяющую те же две вершины. Всякая непростая цепь содержит цикл. Петля - цикл.

17 Граф называется связным, если для любых его двух вершин v и w существует простая цепь из v в w. Бинарное отношение на множестве вершин графа, заданное как «существует путь из v в w », является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Несвязный граф состоит из нескольких связных компонент. Если у графа ровно одна компонента связности, то граф связный.

18 Гамильтоновы графы Гамильтонов граф - граф, в котором есть гамильтонов цикл. Гамильтонов цикл - цикл в графе, содержащий все вершины графа ровно по одному разу. a b c d гамильтонов граф

19 Критерий же существования гамильтонова цикла в произвольном графе еще не найден. Решение этой проблемы имеет практическую ценность, так как к ней близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован в том, чтобы затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. Большинство известных теорем имеет вид "если граф имеет достаточное число ребер, то граф является гамильтоновым графом". Вероятно, самой знаменитой из этих теорем является теорема Дирака. Teoрема 1. Если в связном графе число вершин n 4 и стерень каждой вершины d(x i ) n/2, то граф является гамильтоновым.

20 Эйлеровы графы Граф называется эйлеровым, если существует замкнутая цепь содержащий по одному разу каждое ребро заданного графа (эйлеров цикл). Теорема 2. Связный граф обладает эйлеровым циклом, только когда степени всех его вершины - четные. Доказательство: Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь придет в вершину, столько и выйдет, причем уже по другому ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно результат подсчета входов в вершину, другое выходов.

21 a b cd f e эйлеров граф a b cd e не эйлеров граф

22 Признак эйлерова графа для ориентированного графа: a bcde f Теорема 3. Связный ориентированный граф обладает эйлеровым циклом, только когда у каждой вершины входящая и исходящая степени равны. эйлеров граф

23 I Задача о мостах Кёнигсберга: Город Кёнигсберг (ныне Калининград) состоял из независимых городских поселений, расположенных на двух островах и берегах реки Прегель. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды, и вернуться в исходную точку?

24 В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно). Леонард Эйлер ( ) Эйлер пришёл к следующим выводам: Число нечётных вершин графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

25 мультиграф кёнигсбергских мостовсоответствующий граф

26 Дополнительные характеристики графов Граф называется: деревом, если он связный и не содержит циклов. деревья a b c d e f a b c d e f

27 двудольным, если его вершины можно разбить на два непересекающихся подмножества V 1 и V 2 так, что всякое ребро соединяет вершину из V 1 с вершиной из V 2 ; полным двудольным K m,n, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества. Граф называется: Заметим, что граф K m,n имеет ровно m+n вершин и mn ребер. abcd e K 4,3 f g a b c d e f K 1,5

28 планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер. a b c d e планарный граф изоморфный ему граф без пересечений рёбер = плоский граф a b c d e

29 Подграф Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все рёбра принадлежат E(G). K 5 - полный граф на 5-ти вершинах a b c d e a c d e подграф графа K 5

30 Дополнение графа - граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет. a b c d e a b c d e исходный граф дополнение

31 Базис графа B: минимальное множество вершин, из которых каждая вершина графа досягаема. a b c d e базис В = {e, b}

32 Поиск минимальных разбиений Часто решение логических задач связывается с поиском некоторой совокупности подмножеств заданного множества, удовлетворяющей определённым требованиям, и оптимальной в том или ином смысле, например минимальной по числу выбранных подмножеств. Задано некоторое множество V. На множестве V определено отношение несовместимости. Требуется найти такое разбиение множества V на минимальное число подмножеств (блоков) так, чтобы любые два элемента принадлежащие одному блоку не находились бы в отношении несовместимости. Пример. Поиск разбиения сводится к раскраске графа описывающего отношение несовместимости.

33 Пример. Задача размещения отдыхающих. Задано отношение несовместимости на множестве V = {v 1, v 2, v 3, v 4, v 5 } Получаем разбиение: V = { { v 1, v 2, v 3 }, { v 4, v 5 } } v2v2 v4v4 v5v5 v3v3 v1v1

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

35 Теорема. Для оптимальной раскраски планарных графов достаточно четырёх цветов. (1977, K. Appel, W. Haken, J. Koch) Решение путем сведения к задаче о кратчайшем покрытии. Данная задача сводится к поиску минимального числа максимальных пустых подграфов, которые в своей совокупности содержат все вершины заданного графа. Утверждение. Вершины, которые не принадлежат пустому подграфу, должны покрывать все ребра заданного графа (действительно, иначе обе вершины непокрытого ребра должны принадлежать этому подграфу, что невозможно). На основании приведенного утверждениия построение пустого подграфа можно свести к поиску подмножества вершин покрывающего все ребра заданного графа.

36 Алгоритм 1. Найти все максимальные пустые подграфы графа G. 2. Построить матрицу бинарного отношения принадлежности вершин графа найденным подграфам. 3. Найти кратчайшее покрытие этой булевой матрицы. 4. Перейти к разбиению множества вершин (т.е. устранить возможные пересечения между множествами вершин выбранных максимальных пустых подграфов).

37 Пример. 1. Построение максимальных пустых подграфов. fe (1, 2, 3, 4, 5) = (1 5) & (2 4) & (1 4) & (3 5) = = (1&2&3) (1&3&4) (1&2&5) (4&5) Минимальные подмножества вершин покрывающие все ребра будут: {1, 2, 3}, {1, 3, 4}, {1, 2, 5}, {4, 5} Взяв дополнения найденных подмножеств, получим все максимальные пустые подграфы: G1 = {4, 5}, G2 = {2, 5}, G3 = {3, 4}, G4 = {1, 2, 3} Дан граф:

38 2. Построение матрицы бинарного отношения принадлежности вершин графа найденным подграфам G G G G Решение задачи покрытия. Минимальное покрытие будет: {G1, G4} Таким образом имеем решение: {{4, 5}, {1, 2, 3}}