Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в
K5 или K3,3.
19 Алгоритмы отыскания кратчайших путей в графе. Минимальны остов.
Алгори́тм Де́йкстры
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.
Минимальное остов в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
В терминах матрицы эффективности задача состоит в нахождении М элементов, расположенных в разных строках и разных столбцах, чтобы их сумма была максимальной.
Дан двудольный полный граф с V = M, W = M
Даны длины ребер.
Задача состоит в нахождении совершенного паросочетания, сумма длин всех ребер которого максимальна.
Алгоритм.
1. Всем вершинам Vi даем метку аi = max по всем элементам нужной строки.
По всем j присваиваем метку 0.
2. Ищем ребра, для которых выполняется условие
Ai + Bj = Aij
Строим граф, в который входит все вершины исходного графа и найденные ребра.
3. В построенном графе ищем максимальное паросочетание. Если найденное паросочетание совершенно, то алгоритм закончен. Если нет, то переходим дальше.
4. Из теоремы Холла существует подмножество S из V, [S] > ф(S).
Ищем это подмножество.
Для каждой вершины Vi из S метку Ai уменьшают на 1, а для wj из ф(s) метку Vj увеличивают на 1.
5. Переходим на начало шага 2 с новыми значениями меток.