20: Двудольные графы. Паросочетания Двудольные графы

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

Теорема. Граф двудольный тогда и только тогда, когда в нём нет циклов нечётной длины.

Доказательство. Пусть граф имеет цикл нечётной длины. Первую вершину цикла занесём в первую долю, следующую — во вторую и т. д. Т. к. цикл нечётной длины, последняя вершина цикла будет одной доли с первой, что противоречит определению двудольного графа.

Доказательство в обратную сторону. Начнём обход в ширину, чередуя занесение в ту или иную долю при увеличении расстояния от начальной вершины . Некоторая вершина может быть соединена с некоторой вершиной на расстоянии . Если , то можно найти общего предка этих вершин, что . Тогда длина цикла через вершины будет равна — нечётному числу.

Паросочетания

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

Насыщенная вершина — вершина, инцидентная ребру из паросочетания.

Свободная вершина — вершина, не инцидентная ребру из паросочетания.

Совершенное паросочетание — паросочетание, где все вершины графа насыщенные.

Алгоритм построения максимального паросочетания двудольного графа

Ввести фиктивные вершины и , соединив S с вершинами первой доли, а T — второй доли.
Ориентировать все рёбра от S к первой доле, от первой доли ко второй, от второй доли к T.
Пока существует путь от S к T
1. Изменить ориентацию рёбер вдоль этого пути
2. Удалить рёбра, инцидентные фиктивным вершинам
Рёбра, ориентированные от второй доли к первой — искомое паросочетание.

21: Остовные деревья. Алгоритм Прима.

стр. 292

Алгоритм ищет минимальное остовное дерево графа.

Остовное дерево — дерево, являющееся подграфом графа и содержащее все его вершины.

Алгоритм.

22: Остовные деревья. Алгоритм Краскала.

Алг. 2.16 стр. 294-296

Остовное дерево — дерево, являющееся подграфом графа и содержащее все его вершины.

23: Алгоритм Дейкстры

Ищет минимальный путь между источником и остальными вершинами.

Инициализация:

Устанавливаем всем вершинам длину пути на максимальную.
Устанавливаем источнику длину пути на 0.

Основной алгоритм:

Пока есть необработанные вершины
1. Находим необработанную вершину , у которой кратчайшая длина пути.
2. Для всех смежных с вершин :
  1. Изменяем текущую длину пути до на сумму длины и длины пути до , если эта сумма меньше.
3. Помечаем вершину обработанной.

Теорема. Алгоритм Дейкстры ищет кратчайшие пути от источника до остальных вершин. Доказательство. Рассмотрим минимальный путь На первом шаге алгоритма Заметим, что сопоставляемая длина пути может только уменьшаться в процессе. Когда мы начинаем обрабатывать , то к этому моменту , а для путь станет . Получается при обработке для путь станет . Но так как мы рассматриваем минимальный путь, то . Значит алгоритм действительно работает корректно.