Графы. Задание графа

Источники
Аляев Ю. А., Тюрин С. Ф. Дискретная математика и математическая логика.
Андерсон Дж. Дискретная математика и комбинаторика.
Хаггарти Р. Дискретная математика для программистов.

Задание графа

Граф

Орграф

Задание графа

Задание графа

Задание графа

Задание орграфа

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

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

Степень (валентность) вершины

Полустепень

Теорема

Теорема

Особые графы

Турнир
Ориентированный граф, в котором любая пара вершин соединена ровно одной дугой, т. е. орграф, ассоциированным графом которого является полный граф.
Любой турнир содержит гамильтонов путь. Строго связный турнир имеет гамильтонов цикл.

Сколько ребер у полного n-графа?

Сколько ребер у полного n-графа?

Мультиграфы и псевдографы

Петли

Кратные рёбра
Если в графе существуют несколько рёбер, соединяющих одну и ту же вершину, то такие рёбра называются кратными.
Граф, содержащий кратные рёбра называется мультиграфом.

Псевдограф
Мультиграф, содержащий петли называется псевдографом.

Двудольный граф

Двудольные графы

Полным двудольным графом называется специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
Полный двудольный граф
K4,3
K5,1

Маршруты и пути

Маршрут

Маршрут

Цепь

Цикл

ПРИМЕР
abdbc – маршрут, но не цепь;
abdcb – цепь, но не простая цепь;
abcde – простая цепь;
abdbca – замкнутый маршрут, но не цикл;
abfedbca – цикл, но не простой цикл;
abca – простой цикл.

Определить
2,3,4,5,1,2- цикл?
2,3,5,4 – маршрут?
НЕТ
2,3,4,5,1,4,3- маршрут?
ДА
а цепь?
НЕТ
3,1,4,5,1,2- цепь?
ДА
простая?
НЕТ
2,3,1,4,3,1,2 – цикл?
НЕТ
замкнутый маршрут?
ДА
2,3,1,4,5,1,2- цикл?
ДА
простой?
НЕТ
ДА
простой?
ДА

Каждая внутренняя вершина незамкнутой цепи инцидентна не менее, чем рёбрам, концевые вершины инцидентны минимум одному ребру.
Если в графе степень каждой вершины не меньше 2, то в нем есть цикл.
Число вершин в маршруте на единицу больше числа рёбер, тогда как в цикле число рёбер равно числу вершин.
Свойства

Свойства

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

Путь

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

Связность

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

Пример

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

Матрицы связности и достижимости

Матрицы связности и достижимости

Эйлеров граф

Задача о семи кёнигсбергских мостах
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В письме итальянскому математику и инженеру Мариони от 13 марта 1736 года Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

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

Эйлеров цикл и Эйлерова цепь
Цикл называется эйлеровым, если он содержит все ребра графа.
Граф называется эйлеровым, если в нем найдётся эйлеров цикл.
Связный граф является эйлеровым тогда и только тогда, когда он не содержит вершин нечётной степени.
Цепь, содержащая все ребра графа, называется эйлеровой.
Граф, обладающий эйлеровой цепью, называется квазиэйлеровым.
Граф является квазиэйлеровым, если в нем не более двух вершин нечётной степени.
В квазиэйлеровом графе существующие у него две вершины нечётной степени всегда будут являться концами любой эйлеровой цепи.

Эйлеровы графы

Гамильтонов граф

Гамильтонов граф

Игра "Вокруг света"

Критерий существования гамильтонова цикла в произвольном графе еще не найден.
Факты о существовании гамильтоновых циклов в графе:
Всякий полный граф является гамильтоновым
Если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие ребра, то он также является гамильтоновым.
Если гамильтонов граф объединить с ещё одной вершиной ребром так, что образуется висячая вершина, то такой граф гамильтоновым не является,
Не является гамильтоновым и граф, представляющий собой простой цикл с "перекладиной" (тэта граф), на которой расположены одна или несколько вершин.
Гамильтонов граф

Деревья

Определения
Дерево - связный, неориентированный граф без циклов.
Лес – граф, компоненты которого являются деревьями.

G1 – дерево
G2 – не дерево
G3 – не дерево
Какой из графов является деревом?

Листья

Свойства деревьев

Свойства деревьев

Корень дерева
Пусть дерево представляет физический объект, подвижный в вершинах.
Если подвесить дерево за одну из вершин, остальная часть повиснет ниже.
Такая вершина называется корнем дерева.
Если корень дерева определен, то дерево называется корневым деревом.

Корневое дерево

Предки и потомки

Основные соотношения

Поиск в глубину

Поиск в глубину (англ. depth-first search, DFS)

Поиск в глубину

Алгоритм поиска в глубину

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

Поиск в ширину

Поиск в ширину (англ. breadth-first search, BFS)

Поиск в ширину

Применения алгоритма поиска в ширину
Выделение компонент связности (подсчёт компонент);
Поиск кратчайшего пути в невзвешенном графе;
Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа;
Нахождение кратчайшего цикла в ориентированном невзвешенном графе;
Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами.

Числовые характеристики графа

Расстояние между вершинами

Эксцентриситет

Диаметр графа

Радиус графа

Центр графа

Пример

Найти диаметр, радиус и центры графа

Задачи

Перечислить вершины и рёбра графа.

Построить матрицу инцидентности

Построить матрицу смежности

Найти все пары вершин, между которыми существует маршрут длины 2

Найти все пары вершин, между которыми существует маршрут длины 3

Найти все пары вершин, между которыми существует маршрут длины не меньше 3

Определить количество маршрутов длины 2