Элементы теории графов

Основные разделы:
4.1 Основные определения и понятия
4.2 Способы задания графа
4.3 Операции над графами и их свойства
4.4 Деревья
4.5 Обходы
4.6 Алгоритмы на графах

Теория графов как математическая дисциплина сформировалась в середине 30-х гг. ХХ ст. Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г.
При использовании понятия «граф» в математике чаще всего имеют в виду графическое определение (задание) связей между объектами произвольной природы.
Денеш Кёнинг (1884-1944)

Анализ и синтез цепей и систем;
проектирование каналов связи и исследование процессов передачи информации;
построение контактных схем и исследование конечных автоматов;
календарное планирование промышленного производства;
Применение

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

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

4.1 Основные определения и понятия

Основные определения и понятия

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

Определения

Смежность и инцидентность

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

Путь, цепь, контур
Цепь (цикл) называется гамильтоновой, если она проходит через все вершины графа по одному разу.
Цепь (цикл) называется эйлеровой, если она проходит через все реб­ра по одному разу. Аналогично определяются гамильтоновы и эйлеровы путь и контур.

Связность

Степень вершины графа

Число ребер графа

Следствия

Нуль-граф
Полный граф К5
Примеры
Дерево-цепь

Однородным графом является и полный двудольный граф Km,m = G(V1,V2,E), |V1|=|V2 |= m, подграфы которого G1(V1,∅) и G2(V2,∅) – нуль-графы и все вершины подмножеств V1 и V2 попарно соединены ребрами.
На рисунке граф K3,3

Определение двудольного графа Km,n = G(V1,V2,E),
Двудольный граф Km,n = G(V1,V2,E), - это граф G(V,E), такой что множество V разбито на два непересекающихся подмножества V1 и V2, |V1|=m, |V2 |=n, причем всякое ребро из E соединяет вершину из V1 с вершиной из V2. Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом.

Эйлеровы и гамильтоновы цепи и циклы

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

Эйлерова церь

Алгоритм построения эйлерова цикла

Гамильтонов цикл

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

Свойства изоморфных графов

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

Гомеоморфизм графов

Теорема Понтрягина-Куратовского
Теорема 3. Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам К5 и К3,3.

Числа, характеризующие граф

Хроматическое число графа

Задача о раскраске географической карты

4.2. Способы задания графа
Графически;
На языке теории множеств;
Матричным способом;
Списками.

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

Для орграфа:

Для неорграфа:

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

Матрица инцидентности

Матрица инцидентности

Матрица инцидентности

Матрица инцидентности

v1: v2, v3, v4
v2: v4
v3:
v4: v1, v3
Задание списком смежностей

e1: v1, v2
e2: v1, v3
e3: v1, v4
e4: v4, v1
e5: v2, v4
e6: v4, v3
Задание списком инцидентностей (ребер)

4.3 Операции на графах и их свойства
1. Удаление ребра;
2. Удаление вершины;
3. Добавление вершины;
4. Добавление ребра;
5. Отождествление вершин;
6. Стягивание ребра;
7. Размножение вершины;
8. Расщепление вершины;
9. Дублирование вершины;
10. Разбиение ребра (гомеоморфизм);
11. Дополнение графов;
12. Объединение графов;
13. Пересечение графов;
14. Соединение графов;
15. Композиция графов;
16. Произведение графов.

1-4 Операции добавления и удаления

5-6 Операция отождествления вершин

Операции на графах 7-9

Операции на графах 7-9

11 - Дополнение графов

Дополнение графов

Пример 1. Матрицы смежности вершин А графа G2 и графа , изображенных на рис., имеют вид:

Объединение графов-12

Объединение графов

Объединение графов

ПРИМЕР 2

ПРИМЕР 2 (продолжение)
Матрицы смежности вершин графов:

ПРИМЕР 2 (продолжение)
матрицы смежности вершин вспомогательных графов G1′ и G2′ и графа G:

13- Пересечение графов

Пересечение графов

Пересечение графов

ПРИМЕР 3

ПРИМЕР 3 (продолжение)
Матрицы смежности вершин исходных графов:

ПРИМЕР 3 (продолжение) V = V1∩V2 = {1, 2, 3}.
Матрицы смежности вершин вспомогательных графов G1′ и G2′ и графа G :

14- Соединение графов

Соединение графов

15- Композиция графов

Композиция графов

ПРИМЕР 5: Представление в табличной форме (списком дуг)

Пример 5 Матрицы смежности вершин исходных графов

Пример 5

4.4 Деревья

Ориентированные деревья
Ориентированные деревья

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

Доказательство

Задача о нефтепроводе
(минимальном остовном дереве)

Задача о нефтепроводе: построение графа

Задача о нефтепроводе: графическая задача

Алгоритм Краскала (жадный)

Алгоритм Прима (алгоритм ближайшего соседа)
Идея алгоритма. На каждом шаге алгоритма будем достраивать остовное дерево T(Vt, Et) следующим образом: к множеству ребер уже построенного дерева добавляем ребро минимального веса, один конец которого находится в множестве Vt , а второй — в множестве V \ Vt .