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

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

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

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

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


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

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

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



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

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

Теперь познакомимся с основными понятиями из теории графов.
Определение 7.1. Графом G=G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множество E двухэлементных подмножеств множества V. Множество E называется множеством ребер.
Вершины v_i и v_j множества V называются соединенными ребром (v_i, v_j) или инцидентны к ребру (v_i, v_j), если (v_i, v_j)E. Если (v_i, v_j) – ребро, тогда вершины v_i и v_j называются концами ребра (v_i, v_j). Ребро (v_i, v_j) называется также инцидентным к вершинам v_i и v_j. Две вершины называются смежными, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

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

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

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

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

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

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

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

Определение 7.3. Граф G(V, E) называется подграфом (или