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

Лекция №7.1
План
1. Возникновение теории графов.
2. Основные понятия и определения теории графов.
3.

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

Задачи, приводящие к понятию графа
Подобные схемы впервые назвал «графами» венгерский математик Денеш Кёниг в 1936 г. При этом начало теории графов как отдельной дисциплины было положено еще в 1736 году Леонардом Эйлером в его знаменитом рассуждении о семи Кенигсбергских мостах.
Бывший Кенигсберг (ныне - Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Задача о кенигсбергских мостах
Кенигсберцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз.
Эйлер доказал, что это невозможно и изобрёл таким образом эйлеровы циклы. Однако эта статья была единственной в течение почти ста лет.

Интерес к проблемам теории графов возродился к середине 19 столетия благодаря исследованиям электрических сетей, моделей кристаллов, структур молекул. Большое число популярных головоломок тех времен поддавались формулировкам именно в терминах графов. Одна из них – задача о трех колодцах и трех домах.
Задача о трех колодцах и трех домах
Три соседа поссорились. Все три имеют по колодцу. Возможно ли проложить тропинки от дома каждого соседа к каждому колодцу так, чтобы эти тропинки не пересекались?
Как видим, ответ отрицательный.

Теорема о четырёх красках — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
Эта теорема была сформулирована Фрэнсисом Гутри (англ.) в 1852 году, однако доказать её долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок.
Теорема о четырёх красках

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

Применение графов
Графы применяются:
Банковское дело
Промышлен-ность
Медицина
Молекулярная биология

Лекция доктора технических наук, профессора Владимира Алексеевича Кузнецова
Петрозаводский государственный университет (РФ)
.

Рассмотрим пример.
Пусть V – множество городов России, Е – множество пар аэропортов, между которыми установлено гражданское авиасообщение.
Основные понятия и определения
теории графов
Москва
Санкт-Петербург
Ростов-на-Дону
Екатеринбург
На рисунке 1 изображен граф G=G(V,E).
Рис. 1

Определение графа
Пусть V - непустое множество, состоящее из соединенных некоторым образом точек Xi. Множество V называется множеством вершин
(или узлов).
Обозначим E - множество пар u =(Xi, Xj), где Xi, Xj – элементы множества V. Пара u =(Xi, Xj) называется ребром (дугой).
Графом называется упорядоченная пара G=G(V,E).
Иными словами, граф – это непустое множество точек (вершин) и отрезков (ребер), концы которых принадлежат заданному множеству точек.

Определение графа
Ребро u=(Xi, Xj) называется неориентированным, если (Xi, Xj) = (Xj, Xi).
Ребро u=(Xi, Xj) называется ориентированным (или дугой), если
(Xi, Xj) ≠ (Xj, Xi).
При этом дуга направлена от вершины Xi к вершине Xj.
Xi – начало, Xi – конец дуги.
Ребро (дуга) называется петлёй, если его концы совпадают, то есть u =(Xi, Xi).

Определение графа
Множество V, а значит и множество E, обычно считаются конечными множествами. Граф называется конечным, если он имеет конечное число вершин (рис 2). В противном случае граф называется бесконечным (рис. 3).
Рис. 2
Рис. 3
Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов, поскольку не все утверждения, имеющие место для конечных множеств, выполняются в случае бесконечных множеств.

Определение графа
Вершины и рёбра графа называются также элементами графа,
число вершин в графе, т.е. |V| называется порядком графа,
число рёбер, т.е. |E| - размером графа.

Определение графа
Две концевые вершины одного и того же ребра называются смежными.
Если u =(Xi, Xj), то ребро u инцидентно вершинам Xi и Xj, а вершины Xi и Xj инцидентны ребру u.
Вершины Xi и Xj называются концевыми вершинами (или просто концами) ребра u =(Xi, Xj).

Определение графа
Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды). Обозначают: ρ(Xi).
Вершина называется изолированной, если она не принадлежит ни одному ребру, т.е. ρ(Xi)=0;
вершина называется висячей (или листом), если она принадлежит ровно одному ребру, т.е. ρ(Xi)=1.
Граф, состоящий только из изолированных вершин, называется нуль-графом. Нуль-граф не содержит ребер.

Виды графов
Граф G=G(V,A) называется ориентированным (или орграфом), если все его связи заданы дугами (рис. 4). A – множество дуг.
Граф G=G(V,E) называется неориентированным, если все его связи заданы ребрами (рис. 5). E – множество ребер.
Граф G=G(V,E,A) называется смешанным, если он содержит ребра и дуги (рис. 6).
Рис. 4
Рис. 6
Рис. 5

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

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

Плотный граф – полный граф, у которого при каждой вершине имеется петля.
Плотный граф

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

Изоморфные графы

Способы задания графов
Геометрический.
Пусть задан граф G=G(X,V).
Графы имеют наглядную геометрическую интерпретацию в виде диаграмм, состоящих из точек и линий, соединяющих некоторые из этих точек. Точки соответствуют вершинам графа (элементам множества X), а линии – его ребрам (дугам). При этом форма и длина линий значения не имеют. Важно лишь, что две данные точки соединены или не соединены линией.

Способы задания графов
Геометрический
Пример:
Рис. 1 Рис. 2

Способы задания графов
Аналитический.
Всякий граф G=G(X,V) можно рассматривать как совокупность множества элементов X и подмножества V упорядоченных пар (Xi, Xj) декартового произведения X×X, т.е. V ⊆ X2. Таким образом, аналитически граф можно считать бинарным отношением, заданным на множестве X.

Способы задания графов
Аналитический.
Чтобы задать граф аналитически, необходимо указать:
Множество вершин X.
Множество ребер (дуг)
V={(Xi, Xj)| Xi, Xj ∈ X} .
3) Множество изолированных вершин.

Способы задания графов
Аналитический.
Пример: