Лекции по "Развитию операционных систем"

Лекция 6.

 

п.7.  Графы. Орграфы.

 

7.1.  Графы и орграфы. Основные понятия.

 

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

Теория графов многократно «открывалась» разными авторами при решении различных прикладных задач.

Но полноправно можно сказать, что теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).

Задача о кенигсбергских мостах.

 

Жителям Кенигсберга нравилось гулять по дорожкам, которые включали семь мостов, соединяющие два острова и берега реки Преголя. Люди интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реку. Для решения задачи Эйлер построил граф: участки суши изобразил вершинами, а дорожки через мосты – как ребра. Сначала им была сформулирована и доказана теорема. И опираясь на эту теорему, Эйлер показал, что такого маршрута нельзя построить. Далее мы рассмотрим, как Эйлер решил эту задача.

Кроме задачи о кенигсбергских мостах, классическими задачами стали: задача о трех домах и трех колодцах; задача о четырех красках.

Задача о трех домах и трех колодцах.  Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) К Куратовским (1896 – 1979) в 1930 году.

Задача о четырех красках.  Разбиение плоскости на непересекающиеся области называется картой. Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которая базировалось на переборе вариантов с помощью компьютера.

Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.

 

Теперь познакомимся с основными понятиями из теории графов.

 

Определение 7.1.  Графом G=G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множество E двухэлементных подмножеств множества V. Множество E называется множеством ребер.

 

Вершины vi и vj множества V называются соединенными ребром (vi, vj) или инцидентны к ребру (vi, vj), если (vi, vj)ÎE. Если (vi, vj) – ребро, тогда вершины vi и vj называются концами ребра (vi, vj). Ребро (vi, vj) называется также инцидентным к вершинам vi и vj. Две вершины называются смежными, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

Число вершин графа G обозначим v, а число ребер - e:

.

 

Определение 7.2.  Ориентированный граф или орграф G=G(V, E) – это такой граф, который состоит из множества V вершин и множества E упорядоченных пар элементов из V. Элемент множества E называется дугой. Если (vi, vj)ÎE, то vi называется начальной вершиной дуги (vi, vj), а vj называется конечной вершиной.

 

Геометрическое представление графов следующее:

1)  вершина графа – точка  в пространстве (на плоскости);

2)  ребро неориентированного  графа – отрезок;

3)  дуга ориентированного графа  – направленный отрезок.

 

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

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

 

Определение 7.3.  Граф G¢(V¢, E¢) называется подграфом (или частью) графа G(V,E), если V¢ ÍV, E¢ ÍE. Если V¢=V, то G¢ называется остовным подграфом G.

 

Аналогично, как и для графа, для орграфа вводится понятие ориентированный подграф.

 

Пример 7.1.  Дан неориентированный граф.

 

,

 

Определение 7.4.  Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через Kn.

Определение 7.5.  Граф G=G(V, E) называется двудольным, если V можно представить как объединение непересекающихся множеств, скажем V=AÈB, так что каждое ребро имеет вид (vi, vj), где viÎA и vjÎB. Двудольный граф называется полным двудольным графом Km, n, если A содержит m вершин, B содержит n вершин и для каждого viÎA, vjÎB имеем (vi, vj)ÎE.

Пример 7.2.  Построить полный двудольный граф K2,4 и полный граф K4.

 

,

 

 

7.2.  Связность графов.

 

Определение 7.6.  Пусть G=G(V, E) – граф с вершинами v0, v1, v2, …, vnÎV и ребрами e1, e2, …, emÎE. Маршрутом (путем) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…vk-1ekvk такая, что ei=(vi-1, vi).

Таким образом, путь длины k имеет k ребер. По причине избыточности обозна-чений в этом определении для графа в общем случае путь будет обозначаться через v0v1v2…vk.

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

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

Пример 7.3.  Дан неориентированный граф.

,

 

Определение 7.7.  Граф G=G(V, E) называется связным, если имеется цепь между любыми двумя его различными вершинами.

 

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

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

 

 

7.3.  Изоморфизм графов.

\

Определение 7.9.  Функция f : G(V, E) ® G1(V1, E1) является изоморфизмом (обозначается G~G1), если f: V®V1 и f: E® E1 представляют собой взаимно однозначные соответствия. Если f:G®G1 – изоморфизм, то G и G1 называются изоморфными.

Пример 7.4.  Дан неориентированный помеченный граф G1(V1; E1). Построить изоморфные ему графы.

 

 

Решение.

,

 

Теорема 7.1.  Изоморфизм графов есть отношение эквивалентности.

Доказательство.  Действительно, изоморфизм обладает всеми необходимыми свойствами отношения эквивалентности:

[Рефлексивность.]  G ~ G, где требуемая биекция есть тождественная функция;

[Симметричность.]  Если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h- 1;

[Транзитивность.]  Если G1 ~ G2 с биекцией h и G2 ~ G3 с биекцией g, то G1 ~ G3 с биекцией g o h.

■

 

 

7.4.  Степень вершин.

 

Определение 7.10.  Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей.

 

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

Теорема 7.2. (Теорема Эйлера)  Сумма степеней вершин графа равна удвоенному количеству ребер:

.

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

■

Следствие 1.  Число вершин нечетной степени четно.

Доказательство.  По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.

■

Следствие 2.  Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

.

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

■

Пример 7.5.  Определить степени вершин данного графа.

,

Пример 7.6.  Определить полустепени исхода и захода данного орграфа.

,