- Понятие множества
- Способы задания множеств
- Операции над множествами: объединение, пересечение, разность, декартово произведение.
- Размещения различных предметов по различным ящикам с различными ограничениями
- Раскраски различных предметов с различными ограничениями
- Количество слов фиксированной длины в заданном алфавите с различными ограничениями
- Упорядоченные выборки
- Неупорядоченные выборки, число сочетаний (формула с доказательством)
- Количество подмножеств фиксированной мощности
- Определение графа
- Ориентированные и неориентированные графы
- Геометрическая интерпретация графа
- Кратные ребра и петли. Простой граф
- Понятия смежности и инцидентности
- Степень вершины. Теорема о сумме степеней вершин графа, лемма о рукопожатиях
- Полный граф. Количество ребер в полном графе
- Матрицы инциденций неориентированных графов
- Матрицы инциденций ориентированных графов
- Матрицы смежности графов
- Подграф
- Пути и циклы в графе. Связность неориентированных графов
- Компонента связности неориентированного графа
- Алгоритм поиска в глубину
- Алгоритм поиска в ширину
- Задачи, которые можно решать с использованием модифицированных алгоритмов поиска
- Постановка задачи, особенности графов, для которых такую задачу можно формулировать
- Алгоритм Форда-Беллмана. Дерево кратчайших путей.
- Определение эйлерова пути, эйлерова цикла, эйлерова графа
- Критерий существования эйлерова цикла (пути) в графе)
- Алгоритм построения эйлерова цикла в эйлеровом графе
- Определение гамильтонова пути, гамильтонова цикла
- Оценка количества гамильтоновых циклов п полном графе
- Переборный алгоритм нахождения гамильтонова пути в графе, либо доказательства отсутствия ГЦ
Множество (S) – любое собрание определённых и различимых между собой объектов нашей интуиции, мыслимое, как единое целое.
Элементы множества – объекты, составляющие множество (числа, функции, множества внутри множеств).
Универсальное множество (U, универсум) – множество, содержащие в себе все другие возможные объекты.
Пустое множество (Ø) – множество, не содержащее в себе элементов
Парадокс: если универсум содержит все множества и сам является объектом, то он должен содержать сам себя.
Обозначения:
- 𝑥 ∈ 𝐴 – объект x принадлежит множеству А
- 𝑥 ∉ 𝐴 – объект x не принадлежит множеству А
- 𝐴 = 𝐵 – множество А равно множеству В, то есть А состоит ровно из тех же элементов, что и В
-
Перечисление: 𝐴 = {𝑎, 𝑏, 𝑐} – a,b,c являются элементами множества, и только они
- При перечислении элементов множества порядок их перечисления не важен: {𝑎,𝑏, 𝑐} = {𝑏, 𝑐, 𝑎} = {𝑐,𝑎, 𝑏}
- Перечисление невозможно, если:
- Рассматриваемое множество состоит из элементов, которые нельзя указать по какой-то причине
- Множество содержит бесконечное число элементов
- Множество содержит слишком большое число элементов
-
Указание свойства: 𝐵 = {𝑥: 𝑥 − чётное число} – B является множеством чётных чисел. Способ сопоставим с предикатом P(x), принимающим значения «ИСТИНА-ЛОЖЬ»
-
Комбинированный:
- С неполным перечислением: 𝐸 = {𝑒1, 𝑒2, … , 𝑒𝑛}
- Буквенные обозначения:
- ℕ − множество натуральных чисел
- ℤ − множество целых чисел
- ℚ − множество рациональных чисел
- ℝ − множество действительных чисел
- ℂ − множество комплексных чисел
- Дополнение: 𝐵 = 𝐴̅
- Объединение: 𝐶 = 𝐴 ∪ 𝐵
- Пересечение: 𝐷 = 𝐴 ∩ 𝐵
- Разность: 𝐸 = 𝐴\𝐵 = 𝐴 ∩ 𝐵
- Симметрическая разность: 𝐹 = 𝐴Δ𝐵 = 𝐵Δ𝐴 = (𝐴 ∪ 𝐵)(𝐵 ∪ 𝐴)
- Декартово произведение: 𝐴 = {𝑎, 𝑏, 𝑐} } ⇒ 𝐹 = 𝐴 × 𝐵 = 𝐵 = {1,2}
Декартов квадрат: 𝐵 × 𝐵 = 𝐵2
Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Основные задачи комбинаторики:
- Исследование задачи существования данной конфигурации
- Подсчёт числа конфигураций
- Приближённый подсчёт числа конфигураций
- Перечисление конфигураций
- Оптимизация
- Конструирование и анализ комбинаторных алгоритмов
Если объект А может быть выбран m способами, а объект В – n способами, то при условии, что одновременный выбор А и В невозможен, выбор «А или В» можно осуществить m + n способами
Пример: на собрании присутствуют 10 мужчин и 15 женщин. Чтобы выбрать кого-то одного председателем, существует 10 + 15 = 25 способов выбора.
Если объект A может быть выбран m способами, и после каждого такого выбора объект B в свою очередь может быть выбран n способами, то выбор «A и В» в указанном порядке можно осуществить m * n способами
Пример: в ресторане клиент выбирает из 10 первых блюд и из 14 вторых.
Выбрать набор, в который входят и первое, и второе, клиент может 10 * 14 = 140 способами.
Факториал натурального числа – произведение всех натуральных чисел от 1 до данного.
- 𝑛! = 1 ∗ 2 ∗ 3 ∗ … ∗ (𝑛 − 1) ∗ 𝑛
- 0! = 1
- (𝑛 + 1)! = 𝑛! (𝑛 + 1)
Для приближённого вычисления факториала используется формула Стирлинга: 𝑛! ≈ 𝑛𝑛𝑒−𝑛√2𝜋𝑛
Перестановка 𝑨𝒏𝒏 – упорядоченная последовательность, составленная из всех предметов из n заданных.
Две перестановки считаются разными, если они отличаются порядком элементов.
Теорема: количество перестановок п элементов равно п! Доказательство: перестановку можно рассматривать как размещение n различных элементов по n различным ящикам при условии, что каждый ящик содержит ровно один элемент.
Количество таких размещений равно 𝐴𝑛𝑛 = 𝑛! Пример: Даны три элемента {1,2,3}, для них существуют следующие перестановки: - 123 - 213 - 312 - 132 - 231 - 321
То есть 6 перестановок: 3! = 1 ∗ 2 ∗ 3 = 6
- Размещение n предметов по k ящикам: Каждый ящик может вместить k предметов. Все предметы должны быть размещены, порядок не важен. При этом могут остаться незаполненные ящики. Каждый предмет размещается в один из k ящиков независимо от других: 𝑘 ∗ 𝑘 ∗ 𝑘 ∗ … ∗ 𝑘 = 𝑘𝑛
- Раскраска р предметов в r цветов: Каждый предмет может быть окрашен ровно в один цвет, краски каждого цвета хватит для окраски всех предметов. Каждый предмет красится независимо от других только в один цвет, значит, число способов перекраски равно 𝑟𝑝
- Количество слов длины t в заданном алфавите длины m: На каждое из t мест символ можно выбрать т способами, таким образом количество слов равно
𝑚 ∗ 𝑚 ∗ … ∗ 𝑚 = 𝑚𝑡 Пример: существует 32 = 9 слов длины 2 в алфавите {1,2,3}:- 11
- 12
- 13
- 21
- 22
- 23
- 31
- 32
- 33
Выборки из n по k – k-элементные подмножества данного n-множества
- Упорядоченные выборки – выборки, в которых важен порядок элементов:
{𝑎, 𝑏,𝑐} ≠ {𝑐, 𝑏, 𝑎} - Неупорядоченные выборки – выборки, в которых не важен порядок элементов:
{𝑎, 𝑏,𝑐} = {𝑐, 𝑏, 𝑎} Количество неупорядоченных выборок равно С𝑘𝑛 – числу сочетаний из n по k - Количество подмножеств фиксированной мощности: число подмножеств множества А равно 2𝑛. С другой стороны, просуммируем количество k-элементных подмножеств при 0 ≤ 𝑘 ≤ 𝑛.
Получим равенство: С0𝑛 + С1𝑛 + ⋯ + С𝑛𝑛 = 2𝑛
Пусть 𝑉={𝑣1,𝑣2,...,𝑣𝑛} – множество.
Объект вида (𝑣𝑖,𝑣𝑗)называется парой элементов множества V.
Пусть E–множество: 𝐸={𝑒1,𝑒2,...,𝑒𝑚}, элементы которого являются парами вершин: 𝑒1=(𝑣𝑖,𝑣𝑗),𝑒2=(𝑣𝑘,𝑣𝑙),𝑒3=(𝑣𝑘,𝑣𝑙),𝑒4=(𝑣𝑧,𝑣𝑧),
Пара (𝑉,𝐸) называется графом и обозначается 𝐺=(𝑉,𝐸)
Элемент множества 𝑉 называется вершиной графа.
Запись 𝑣𝑖∈𝑉 обозначает, что 𝑣𝑖 является вершиной графа 𝐺=(𝑉,𝐸).
Множество 𝑉 – множество вершин.
Элемент набора 𝐸 называется ребром графа. Запись 𝑒𝑗∈𝐸 обозначает, что 𝑒𝑗 является ребром графа 𝐺=(𝑉,𝐸). Набор 𝐸-набор ребер.
Если все пары в 𝐸 неупорядоченные ((𝑢,𝑣)=(𝑣,𝑢)={𝑢,𝑣}), то граф 𝐺 называется неориентированным.
Если каждая пара в 𝐸 упорядочена ((𝑢,𝑣)≠(𝑣,𝑢)), то граф 𝐺 называется ориентированным графом, или орграфом.
Для оргафов используют обозначение G⃗=(V⃗,E⃗). Элементы E⃗ называются ориентированными ребрами, или дугами, элементы V ⃗ –узлами.
Геометрическая реализация (геометрическая интерпретация) – его изображение на плоскости.
Каждой вершине графа сопоставляется точка, а каждому ребру, т.е. паре вершин – непрерывная не самопересекающаяся кривая, соединяющая эти вершины.
В случае ориентированного графа на кривой указывают направление от начальной вершины дуги к конечной.
Если в множестве 𝐸 есть несколько ребер, заданных одной и той же парой (𝑣,𝑢) называется кратным ребром.
Количество вхождений ребра – его кратность.
Если в множество 𝐸 входит ребро, заданное парой(𝑣,𝑣), то такое ребро пара называется петлей.
Псевдограф – допускаются петли и кратные ребра. Мультиграф – допускаются только кратные ребра. Простой граф – в графе нет ни петель, ни кратных ребер.
Если 𝑒=(𝑢,𝑣) – ребро графа 𝐺, то вершины 𝑢 и 𝑣 называются смежными (соседними) или концами ребра 𝑒.
В случае ориентированного графа для дуги 𝑒⃗= (𝑢,𝑣⃗⃗) вершина 𝑢–начальная, вершина 𝑣–конечная.
Также говорят, что дуга 𝑒⃗ исходит из вершины 𝑢 и заходит в вершину 𝑣.
Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро 𝑒 (дуга 𝑒⃗) инцидентно вершинам 𝑢 и 𝑣, а также, что вершины 𝑢 и 𝑣 инцидентны ребру 𝑒 (дуге 𝑒⃗).
Степень вершины (локальная степень вершины) – количество ребер, инцидентных ей. Договоримся петлю учитывать дважды.
Вершина, не инцидентная никакому ребру, называется изолированной.
Граф называется конечным, если число его ребер конечно.
При таком определении конечный граф может иметь бесконечное число вершин, но все они, кроме конечного числа, изолированные.
Теорема. В конечном графе сумма степеней вершин равна удвоенному количеству ребер.
Теорема остается справедливой и при наличии петель, если только в степенях вершин считать их дважды.
- Следствие 1. В конечном графе количество ребер равно полусумме степеней вершин.
- Следствие 2 (лемма о рукопожатиях). В конечном графе число вершин нечетной степени четно. (Количество человек, совершивших нечетное число рукопожатий, четно.)
Полный граф - простой неориентированный граф с 𝑛 вершинами и обозначается 𝐾𝑛, если в нем любые две различные вершины смежны.
Количество ребер в 𝐾𝑛. Степень каждой вершины графа 𝐾𝑛 равна (𝑛−1), а количество ребер равно полусумме степеней вершин, то есть 𝑛(𝑛−1) / 2=𝐶2𝑛.
В теории графов классическим способом представления графа служит матрица инциденций (инцидентностей).
-
Матрицы инциденций неориентированных графов
-
Матрицы инциденций ориентированных графов
-
Матрицы смежности графов.
Граф 𝐻=(𝑈,𝐹) называется подграфом графа 𝐺=(𝑉,𝐸), если 𝑈⊆𝑉,𝐹⊆𝐸.
Пути и циклы можно рассматривать как подграфы графа 𝐺.
Цепь – путь без повторения ребер.
Простой путь – цепь, в которой не повторяются вершины. Нетрудно видеть, что из любой цепи можно выделить простой путь.
Путь называется замкнутым, если 𝑣𝑖0=𝑣𝑖𝑘.
Замкнутый путь называется циклом, если ребра в нем не повторяются.
Цикл называется простым, если вершины, кроме первой и последней, в нем не повторяются.
Длина[𝑢,𝑣]-пути – количество ребер в нем.
По определению граф 𝐺=(𝑉,𝐸), где |𝑉|=1, 𝐸=∅, является связным.
Из определений следует, что
- полный граф является связным;
- связный граф не обязательно полный.
Подграф 𝐻=(𝑈,𝐹) неориентированного графа 𝐺=(𝑉;𝐸) называется компонентой связности графа 𝐺 если:
- граф 𝐻 связный;
- к графу 𝐻 нельзя добавить ни вершины, ни ребра из графа 𝐺, чтобы он остался связным.
Очевидно, что связный граф состоит из одной компоненты.
Дерево – связный граф без циклов (связный ациклический граф).
- Свойство 1. Пусть 𝑇=(𝑉,𝐸)–дерево, 𝑢,𝑣∈𝑉,(𝑢,𝑣)∉𝐸. Если добавить ребро (𝑢,𝑣), то в графе появится цикл.
- Свойство 2. Пусть 𝑇=(𝑉,𝐸)–дерево, 𝑢,𝑣∈𝑉,(𝑢,𝑣)∈𝐸. Если удалить ребро (𝑢,𝑣), то граф перестанет быть связным.
- Свойство 3. Пусть 𝑇=(𝑉,𝐸)–дерево. Если |𝑉|=𝑛, то |𝐸|=𝑛−1.
Доказательство.
Доказательство легко проводится индукцией по числу вершин.
- Для 𝑛 = 1утверждение, очевидно, справедливо.
- Пусть 𝑛 > 1. Тогда в дереве существует концевая вершина 𝑢.
- Удаляя из дерева vи ребро (𝑢,𝑣), инцидентное 𝑢, получим дерево с 𝑛 − 1 вершиной, которое в силу индуктивного предположения имеет 𝑛 − 1 ребра.
- Следовательно, первоначальное дерево имеет𝑛−2+1=𝑛−1 ребро.
Теорема. В дереве любые две вершины связаны единственным простым путем.
Пусть граф 𝐺=(𝑉,𝐸) связный, его подграф 𝐻=(𝑈,𝐹) называется остовным деревом, если
- 𝐻 - дерево;
- 𝑈=𝑉(множество вершин графа 𝐻 совпадает с множеством вершин графа 𝐺).
Если граф не является связным, то множество остовных деревьев его компонент связности называется остовным лесом.
Дано: Граф 𝐺 = (𝑉, 𝐸). Надо: Найти вершину (вершины), обладающую заданным свойством P.
Алгоритм подобен щупальце, пытается дотянуться до самого дальнего элемента
-
Создаём стек вершин для просмотра
-
Создаём список просмотренных вершин
-
Выбираем начальную вершину
-
Упорядочиваем узлы по номеру и берём первую
либо
-
Выбираем произвольную вершину
-
-
Добавляем начальную вершину в стек
-
Пока стек не пуст
- Берём элемент из стека
- Добавляем его в список просмотренных
- Ищем все такие узлы, которые соединены с текущим
- Если узел ещё не посещён и ещё не в стеке
- Добавляем его в стек
Пример кода:
Graph.Nodes = Graph.Nodes.OrderBy(n => n.Id).ToList();
List<Node> visitedNodes = new List<Node>(); // посещённые узлы
Stack<Node> stack = new Stack<Node>(); // стек узлов к обработке
stack.Push(Graph.Nodes[0]); // добавляем первый узел
// пока очередь не пуста
while (stack.Count > 0)
{
Node node = stack.Pop(); // достаём последний узел
visitedNodes.Add(node); // считаем его обработанным
// ищем все такие узлы, который соединены с текущим
foreach (var n in Graph.Connections.Select(t => t.GetPairedNode(node)).Where(n => n != null).OrderBy(n => n.Id))
{
// если узел ещё не посещён и ещё не в стэке
if (!visitedNodes.Contains(n) && !stack.Contains(n))
{
node.Children.Add(n); // добавляем дочерний узел
n.Parent = node; // устанавливаем родительский узел
stack.Push(n); // добавляем узел в стек обработки
}
}
}Алгоритм подобен волне, просматривает ближайшие вершины, потом вершины на расстоянии 2 шагов, 3 и т.д.
-
Создаём очередь вершин для просмотра
-
Создаём список просмотренных вершин
-
Выбираем начальную вершину
-
Упорядочиваем узлы по номеру и берём первую
либо
-
Выбираем произвольную вершину
-
-
Добавляем начальную вершину в очередь
-
Пока очередь не пуста
- Берём элемент из очереди
- Добавляем его в список просмотренных
- Ищем все такие узлы, который соединены с текущим
- Если узел ещё не посещён и ещё не в очереди
- Добавляем его в очередь
Пример кода:
Graph.Nodes = Graph.Nodes.OrderBy(n => n.Id).ToList();
List<Node> visitedNodes = new List<Node>(); // посещённый узлы
Queue<Node> queue = new Queue<Node>(); // очередь узлов к обработке
queue.Enqueue(Graph.Nodes[0]); // добавляем первый узел
// пока очередь не пуста
while (queue.Count > 0)
{
Node node = queue.Dequeue(); // достаём первый узел
visitedNodes.Add(node); // считаем его обработанным
// ищем все такие узлы, который соединены с текущим
foreach (var n in Graph.Connections.Select(t => t.GetPairedNode(node)).Where(n => n != null).OrderBy(n=>n.Id))
{
// если узел ещё не посещён и ещё не в очереди
if (!visitedNodes.Contains(n) && !queue.Contains(n))
{
node.Children.Add(n); // добавляем дочерний узел
n.Parent = node; // устанавливаем родительский узел
queue.Enqueue(n); // добавляем узел в очередь обработки
}
}
}- Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t).
- Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
- Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v.
Пусть 𝐺 = (𝑉, 𝐸) – граф (ориентированный или неориентированный) Пусть каждому ребру 𝑒 сопоставлено некое действительное число 𝑐(𝑒). Тогда 𝑐 называется весовой функцией, а 𝑐(𝑒) – весом ребра 𝑒 (длиной, стоимостью). Граф G с весовой функцией 𝑐 называется взвешенным графом и обозначается 𝐺 = (𝑉, 𝐸, 𝑐).
Весом графа 𝐻 называется число 𝑐(𝐻), равное сумме весов ребер графа 𝐻.
Матрица весов представляет из себя матрицу смежностей, где вместо 0 и 1 указаны веса рёбер соединяющих вершины.
Остовное дерево с минимальным весом можно найти, применяя «жадный алгоритм», На каждом шаге выбирается новое ребро с наименьшим весом, не образующее цикл с уже выбранными ребрами.
Процесс останавливается, когда выбрано 𝑛 − 1 ребро.
Очевидно, что выбранные на каждом шаге алгоритма ребра образуют лес - граф, компоненты которого - деревья.
Пример кода:
Graph graph = new Graph(); // создаём временный граф
graph.Nodes.AddRange(Graph.Nodes); // копируем в него все узлы
float sum = 0f;
// сортируем рёбра по весам
var connections = Graph.Connections.OrderBy(c => c.ToString()).GroupBy(c => c.Length).SelectMany(g => g).ToList();
// обрабатываем рёбра
for (var i = 0; i < connections.Count - 1; i++)
{
// добавляем ребро в граф
graph.Connections.Add(connections[i]);
// если в графе появился цикл
if (graph.HasLoop())
{
// удяляем это ребро
graph.Connections.Remove(connections[i]);
}
else
{
sum += connections[i].Length;
}
}Этот алгоритм еще называют «алгоритм ближайшего соседа», он является модификацией «жадного» алгоритма с условием, что на каждом шаге алгоритма выбранные ребра являются ребрами связного графа без циклов (дерева).
Кроме списка ребер остовного дерева будем поддерживать список вершин 𝑈, еще не включенных в дерево. Для каждой вершины 𝑣 ∈ 𝑈 графа поддерживается минимальное расстояние до множества 𝑉 ∖ 𝑈 ранее включенных в него вершин.
Простыми словами:
- Выбираем начальную вершину
- Ищем все вершины, которые на текущий момент соединены с деревом и добавляем ближайшее.
- Повторяем, пока все вершины не окажутся подключенными к дереву
Пример кода:
float sum = 0f;
// текущее дерево графа
List<Node> tree = new List<Node>();
// выбираем случайный узел
Node node = Graph.Nodes[0];
tree.Add(node); // добавляем его в дерево
// пока дерево меньше чем граф
while (tree.Count < Graph.Nodes.Count)
{
// выбираем такие рёбра, которые соединены с деревом, но не ещё не подключены к нему
var connections =
Graph.Connections
.Where(c =>
tree.Contains(c.Node1) && !tree.Contains(c.Node2) ||
!tree.Contains(c.Node1) && tree.Contains(c.Node2)
).OrderBy(c => c.ToString()).ToList();
// сортируем рёбра по весу и выбираем первое
var connection = connections.OrderBy(c => c.Length).First();
sum += connection.Length;
// если дерево содержит 1 узел ребра, добавляем второе и наоборот
if (tree.Contains(connection.Node1))
{
tree.Add(connection.Node2);
}
else
{
tree.Add(connection.Node1);
}
}Задача о кратчайшем пути — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Постановка задачи:
- Дано: Сеть 𝐺 = (𝑉, 𝐸, 𝑐) и две выделенные вершины 𝑠 и 𝑡, |𝑉| = 𝑛, |𝐸| = 𝑚.
- Надо: Найти кратчайший [𝑠, 𝑡]-путь.
- Более общая задача - найти путь между выделенной вершиной и всеми остальными вершинами
Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа.
Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.
Основная идея алгоритма Форда-Беллмана заключается в поэтапном вычислении кратчайших расстояний.
Предположим, есть ориентированный взвешенный граф G, который имеет n вершин и m рёбер, и определена некая вершина v.
Необходимо определить длины самых коротких путей от вершины v до каждой другой вершины.
Зададим массив расстояний d[0 ... n – 1], который по завершению выполнения алгоритма содержит итоговый результат.
d[v] = 0, а другие элементы d[] = inf
Алгоритм состоит из нескольких фаз.
Во всех фазах выполняется просмотр всех рёбер графа, и согласно алгоритму делается попытка релаксации (rеlax, ослабления) по направлению каждого ребра (а, b) стоимости с.
Релаксацией ребра (a, b) называется уменьшение значения d[b] до d[a] + c (если второе значение меньше первого).
Граф, образованный множеством 𝐸 (пары соединённых вершин) и множеством выделенных дуг, можно назвать деревом кратчайших путей из вершины 1 во все остальные вершины.
Эйлеров путь в графе - путь, проходящий через каждое ребро графа в точности один раз
Эйлеров цикл в графе - замкнутый эйлеров путь
Эйлеров граф - граф, в котором есть эйлеров цикл
Эйлеров путь в графе существует тогда и только тогда, когда граф
- Связный
- Содержит не более чем две вершины нечетной степени (0 или 2)
Конечный граф 𝐺 = (𝑉, 𝐸) содержит эйлеров цикл тогда и только тогда, когда одновременно выполнены следующие условия:
- 𝐺 связен;
- Степени всех его вершин четные.
Граф 𝐺 = (𝑉, 𝐸) содержит эйлеров цикл, тогда и только тогда, когда
- Множество его ребер можно разбить на простые непересекающиеся циклы.
Пользуясь последней теоремой Эйлера
- Выбираем любую вершину графа
- Пока есть цикл, проходящий через текущую вершину
- Цикл ищем поиском в глубину
- Добавляем все рёбра цикла в ответ
- Удаляем все вершины из графа
- Цикл ищем поиском в глубину
- Для каждой вершины учтённых на прошлом шаге циклах
- Рекурсивно повторяем шаги 2,3
Гамильтонов путь в графе - путь, проходящий через каждую вершину графа в точности один раз
Гамильтонов цикл в графе - замкнутый гамильтонов путь
Гамильтонов граф - граф, в котором есть гамильтонов цикл
Не известен алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя f(n) шагов.
Худший случай - нет гамильтоновых путей
- В худшем случае в полном графе требуется рассмотреть все перестановки O(n!)
- В худшем случае в неориентированном графе нужно просмотреть (n-1)!/2 перестановок.
Достаточные условия существования гамильтонова цикла (n - число вершин графа, u,v - 2 вершины, deg(u) - степень вершины)
- Теорема Оре
- Если 𝑛 >= 3 и deg(𝑢) + deg(𝑣) >= 𝑛 для любых несмежных 𝑢, 𝑣, то в заданном графе есть гамильтонов цикл.
- Условие Дирака
- Если 𝑛 >= 3 и deg(𝑣) >= 𝑛 / 2 для сех 𝑣, то в заданном графе есть гамильтонов цикл
На основе условий:
- В полном графе каждому гамильтонову циклу соответствует перестановка множества вершин (не одна!).
- И наоборот – каждой перестановке соответствует гамильтонов цикл.
Просматриваем (перебираем) все перестановки множества вершин графа.
Для каждой перестановки проверяем: соответствует ли ей цикл в графе.
Дано: Полный взвешенный граф 𝐺 = (𝑉, 𝐸, 𝑐), |𝑉| = 𝑛.
Надо: Найти гамильтонов цикл с наименьшим весом.
Единственный способ решить эту задачу точно - перебрать все гамильтоновы циклы и выбрать тот, у которого вес наименьший.
-
«Жадная» эвристика. Начинаем из вершины с наименьшим номером, выбираем ребро с минимальным весом, включаем его в путь.
Повторяем, пока все вершины не окажутся в графе. Просмотренные рёбра и есть решение задачи.
-
«Ближайшая вставка» Начинаем из вершины с наименьшим номером, выбираем ребро с минимальным весом, которое в данный момент подключено к дереву, включаем его в путь.
(Примерно как в алгоритме Прима)
-
Использование остовного дерева с минимальным весом.
Построенный цикл будет не более, чем в два раза «тяжелее» оптимального.
- 1 шаг: строим остовное дерево с минимальным весом.
- 2 шаг: удваиваем ребра построенного дерева.
- 3 шаг: в полученном графе строим эйлеров цикл.
- 4 шаг: из полученного цикла удаляем повторяющиеся вершины.
- В результате получится гамильтонов цикл.
Связный граф — граф, в котором есть хотя бы одна пара соединённых вершин.
Сильносвязный граф - граф, в котором для любой пары вершин найдётся прямая связь (ребро). (Аналог полного графа)
Слабосвязный граф - граф, в котором для любой пары вершин найдётся хотя бы 1 маршрут соединяющий их.
Односторонне достижимый граф - граф, в котором для хотя бы 1 пары вершин найдётся путь A-B, но не B-A
Несвязный граф - граф, в котором найдётся хотя бы 1 пара вершин, для которой нельзя построить маршрут, соединяющий их.
Компонента связности - Максимальный связный подграф неориентированного графа
Существуют два вида связности:
- Число вершинной связности – это наименьшее число вершин, удаление которых (вместе с инцидентными ребрами) приводит к несвязному графу.
- Число реберной связности– это наименьшее число ребер, удаление которых приводит к несвязному графу.