На перевод

1 Поиск кратчайшего пути от одной вершины (SSSP)

1.1 Постановка задачи

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Суммарный вес этого пути равен

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

Требуется для каждой вершины [math]v[/math], достижимой из вершины-источника [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:

[math] f^*(v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

Название задачи на английском языке – «Single Source Shortest Path» (SSSP).

1.2 Варианты задачи

Если требуется найти кратчайшие пути не от одной, а от всех вершин - см. поиск кратчайшего пути для всех пар вершин.

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

В зависимости от ограничений на возможные значения весов различают следующие случаи.

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

1.3 Свойства задачи

Решение задачи удовлетворяет принципу оптимальности: если путь [math]P^*(u, w)[/math] является частью кратчайшего пути [math]P^*(u, v)[/math], то [math]P^*(u, w)[/math] является кратчайшим путём от источника [math]u[/math] до вершины [math]w[/math].

Принцип оптимальности означает, что для каждой вершины [math]v[/math] вместо всего кратчайшего пути [math]P^*(u, v)[/math] достаточно хранить его последнее ребро [math]e^*_v[/math]. Отсюда следует оценка объёма памяти [math]O(m)[/math].

1.4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]), вершина-источник [math]u[/math].

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

1. для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
2. для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n)[/math].

1.4.1 Преобразование выходных данных и поиск кратчайшего пути

Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_w[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].

Рёбра [math]e^*_v[/math] могут быть восстановлены за время [math]O(m)[/math] перебором рёбер для каждой вершины:

[math] e^*_v \in \{ (w, v) \in E \mid f^*(v) = f^*(w) + f((v, w)) \}. [/math]

Перебор может осуществляться параллельно.

Для поиска кратчайших расстояний [math]f^*(v)[/math] по набору рёбер [math]e^*_v[/math], необходимо построить из них дерево, на котором выполнить поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации).

1.5 Алгоритмы решения задачи

• Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(m)[/math].
• Алгоритм Дейкстры для ориентированных графов с неотрицательными весами, сложность [math]O(m + n \ln n)[/math].
• Алгоритм Беллмана-Форда для ориентированных графов с произвольными весами, сложность [math]O(mn)[/math].
• Алгоритм Δ-шагания для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n + m + dL)[/math], параллельная сложность [math]O((dL + \ln n) \ln n[/math] со средней работой [math]O(n + m + dL \ln n)[/math].
• Алгоритм Торупа представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(m)[/math].
• В ориентированном ациклическом графе с произвольными весами время поиска кратчайших путей линейное – [math]O(m + n)[/math], алгоритм основан на топологической сортировке графа.

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.

Перечисленные алгоритмы могут использоваться и для решения задачи поиска кратчайшего пути для всех пар вершин графа (для этого необходимо запустить соответствующий алгоритм для каждой вершины графа, что при необходимости можно сделать параллельно), при этом оценка сложности умножается на [math]n[/math].

2 Поиск кратчайшего пути для всех пар вершин (APSP)

2.1 Постановка задачи

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math], [math]e \in E[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Вершина [math]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Суммарный вес этого пути равен

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

Требуется для каждой пары вершины [math](u, v)[/math], для которой вершина [math]v[/math] достижима из вершины [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:

[math] f^*(u, v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

Название задачи на английском языке – «All Pairs Shortest Path» (APSP).

2.2 Варианты задачи

Если требуется найти кратчайшие пути лишь от одной, а не от всех вершин – см. поиск кратчайшего пути от одной вершины.

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

В зависимости от ограничений на возможные значения весов различают следующие случаи.

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

В зависимости от способа организации вычислений возможны следующие варианты:

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

2.3 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

1. для каждой пары вершины [math](u, v)[/math] исходного графа – последнее ребро [math]e^*_{uv} = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
2. для каждой пары вершин [math](u, v)[/math] исходного графа – суммарный вес [math]f^*(u, v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n^2)[/math].

2.3.1 Преобразование выходных данных и поиск кратчайшего пути

Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_{uw}[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].

Рёбра [math]e^*_{uv}[/math] могут быть восстановлены за время [math]O(mn)[/math] перебором рёбер для каждой вершины:

[math] e^*_{uv} \in \{ (w, v) \in E \mid f^*(u, v) = f^*(u, w) + f((v, w)) \}. [/math]

Перебор может осуществляться параллельно.

Для поиска кратчайших расстояний [math]f^*(u, v)[/math] по набору рёбер [math]e^*_{uv}[/math], необходимо для данной вершины [math]u[/math] построить дерево из рёбер [math]e^*_{uv}[/math] и выполнить на нём поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации), общее время для всех пар вершин – [math]O(mn)[/math].

2.4 Алгоритмы решения задачи

• Алгоритм Джонсона для ориентированных графов с произвольными весами, сложность [math]O(mn+ n^2 \ln n)[/math].
• Алгоритм Флойда-Уоршелла для ориентированных графов с произвольными весами, сложность [math]O(n^3)[/math].
• Многократное применение любого алгоритма поиска кратчайшего пути от одной вершины:
  • Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(mn)[/math].
  • Алгоритм Дейкстры для ориентированных графов с неотрицательными весами, сложность [math]O(mn + n^2 \ln n)[/math].
  • Алгоритм Беллмана-Форда для ориентированных графов с произвольными весами, сложность [math]O(mn^2)[/math].
  • Алгоритм Δ-шагания для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n(n + m + dL))[/math], параллельная сложность [math]O((dL + \ln n) n \ln n[/math] со средней работой [math]O(n (n + m + dL \ln n))[/math].
  • Алгоритм Торупа представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(mn)[/math].
  • В ориентированном ациклическом графе с произвольными весами алгоритм основан на топологической сортировке графа, сложность [math]O(mn)[/math].

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.

2.5 Ресурс параллелизма

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

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

• выделение компонент связности;
• выделение подграфов, связанных только «мостами» (рёбрами, удаление которых нарушает связность графа);
• выделение компонент двусвязности, связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
• удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).

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

3 Поиск транзитивного замыкания орграфа

3.1 Постановка задачи

Пусть задан ориентированный граф [math]G = (V, E)[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Вершина [math]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Каждая вершина достижима сама из себя.

Требуется построить транзитивное замыкание [math]G^+ = (V, E^+)[/math] графа [math]G[/math]: ребро [math](v, w) \in E^+[/math] тогда и только тогда, когда в графе [math]G[/math] вершина [math]w[/math] достижима из вершины [math]v[/math].

Эквивалентная формулировка: для данного рефлексивного бинарного отношения [math]R[/math] требуется построить наименьшее по включению отношение [math]R^+[/math], содержащее [math]R[/math] и облагающее свойством транзитивности: если [math]aR^+b[/math] и [math]bR^+c[/math], то [math]aR^+c[/math]. Если исходное отношение [math]R[/math] было симметричным, то [math]R^+[/math] будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.

3.2 Свойства задачи

Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то транзитивное замыкание содержит рёбра [math](v, w)[/math] и [math](w, v)[/math]. В неориентированном графе ребро [math](v, w)[/math] принадлежит транзитивному замыканию в том и только в том случае, когда вершины [math]v[/math] и [math]w[/math] принадлежат одной и той же компоненте связности. Следовательно, для неориентированного графа поиск транзитивного замыкания эквивалентен поиску компонент связности.

Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно. Следовательно, поиск транзитивного замыкания графа [math]G[/math] можно свести к поиску транзитивного замыкания ациклического графа, полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину; на этом принципе основан алгоритм Пурдома.

Граф [math]G[/math] и его транзитивное замыкание [math]G^+[/math] имеют одни и те же компоненты сильной связности (в терминах вершин).

3.3 Алгоритмы решения задачи

В неориентированном графе вершина [math]w[/math] достижима из вершины [math]v[/math] тогда и только тогда, когда они обе принадлежат одной и той же компоненте связности. Транзитивное замыкание сводится к поиску компонент связности графа и может быть найдено следующими алгоритмами:

• последовательным применением алгоритма поиска в ширину за время [math]O(m)[/math];
• с помощью системы непересекающихся множеств за время [math]O(m \alpha(m, n))[/math], с возможностью эффективной многопоточной реализации;
• параллельным алгоритмом Шилоаха-Вишкина за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.

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

• алгоритм Флойда-Уоршелла, сложность [math]O(n^3)[/math] (первый опубликованный алгоритм поиска транзитивного замыкания как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
• многократное применение поиска в ширину, сложность [math]O(mn)[/math];
• алгоритм Пурдома, сложность [math]O(m + \mu n)[/math].

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности.

3.4 Ресурс параллелизма

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

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

• выделение компонент связности;
• выделение подграфов, связанных только «мостами» (рёбрами, удаление которых нарушает связность графа);
• выделение компонент двусвязности, связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
• удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).

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

4 Построение минимального остовного дерева (MST)

4.1 Постановка задачи

Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Подграф, являющийся деревом и проходящий через все вершины [math]G[/math], называется основным деревом. Остовное дерево называется минимальным, если суммарный вес его рёбер является минимальным среди всех остовных деревьев.

Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки. Английское название задачи – Minimum Spanning Tree (MST).

4.2 Варианты задачи

Если исходный граф [math]G[/math] несвязный, то набор минимальных остовных деревьев для всех компонент связности называется минимальным остовным лесом (Minimum Spanning Forest, MSF).

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

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

4.3 Свойства задачи

Веса. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, [math][0, 1][/math].

Существование и единственность. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.

Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].

Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.

Минимальное ребро графа. Если [math]e^*[/math] – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан алгоритм Крускала.

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

Количество рёбер остовного леса для графа с [math]n[/math] вершинами и [math]c[/math] компонентами связности равно [math]n-c[/math]. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.

4.4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные: список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).

Объём выходных данных: [math]O(n)[/math].

4.5 Алгоритмы решения задачи

Существует три классических подхода к решению задачи:

• Алгоритм Борувки;
• Алгоритм Крускала;
• Алгоритм Прима.

Во всех случаях последовательная сложность алгоритма [math]O(m \ln m)[/math] при использовании обычных структур данных. (Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.)

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

• Алгоритм GHS (Gallager, Humblet, Spira) и его последующие версии являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
• Алгоритм Габова и др. использует фибоначчиеву кучу для упорядочения рёбер в алгоритме Борувки. Сложность [math]O(m \ln \beta (m, n))[/math].
• Алгоритм Фредмана и Уилларда предназначен для графов с целочисленными весами и имеет линейную оценку сложности [math]O(m)[/math]. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи (AF-heap).
• Алгоритм Каргера и др. решает задачу в среднем за линейное время [math]O(m)[/math]. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)

Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем [math]O(m \ln n)[/math], как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.

4.6 Ресурс параллелизма

1. Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
2. Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
3. Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

5 Поиск изоморфных подграфов

5.1 Постановка задачи

Пусть заданы два графа [math]G[/math] и [math]H[/math]. Задача поиска изоморфных подграфов состоит в том, чтобы определить, существует ли у графа [math]G[/math] подграф, изоморфный [math]H[/math], и в случае положительного ответа – предъявить хотя бы один такой подграф.

5.2 Свойства задачи

Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.

5.3 Алгоритмы решения задачи

Алгоритм Ульмана решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом

• для фиксированного графа [math]H[/math] время полиномиальное;
• для планарного графа [math]G[/math] время работы линейное (при фиксированном графе [math]H[/math]).

Алгоритм VF2 разработан специально для применения на больших графах.

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

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

Пусть задан (ориентированный или неориентированный) граф [math]G = (V, E)[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. В этом случае вершина [math]v[/math] достижима из вершины [math]u[/math]. Считается, что от вершины [math]u[/math] к себе самой ведёт пустой путь [math]P(u, u)[/math], то есть каждая вершина достижима из самой себя. Непустой путь [math]P(u, u)[/math] называется циклом (замкнутым обходом).

Неориентированный граф называется связным, если все его вершины достижимы из некоторой вершины (эквивалентно, из любой его вершины).

Ориентированный граф называется

• слабо связным, если соответствующий неориентированный граф является связным;
• сильно связным, если всякая вершина [math]v[/math] достижима из любой другой вершины [math]v[/math].

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

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

Мостом в графе называется ребро, удаление которого увеличивает число компонент связности.

Шарниром в графе называется вершина, удаление которой увеличивает число компонент связности.

Связный граф называется вершинно-[math]k[/math]-связным (или просто [math]k[/math]-связным), если он имеет более [math]k[/math] вершин и после удаления любых [math]k-1[/math] из них остаётся связным. Максимальное такое число [math]k[/math] называется вершинной связностью (или просто связностью) графа. 1-связный граф называется связным, 2-связный граф – двусвязным.

Связный граф называется рёберно-[math]k[/math]-связным, если он остаётся связным после удаления любых [math]k-1[/math] рёбер. Максимальное такое число [math]k[/math] называется рёберной связностью графа.

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

6.2 Свойства

Эквивалентные определения компоненты связности:

• все вершины, достижимые из какой-либо выбранной вершины;
• набор вершин, достижимых друг из друга, и не достижимых из других вершин.

Отношение «вершина [math]v[/math] достижима из вершины [math]u[/math]» является отношением эквивалентности. Таким образом, поиск связных компонент графа это то же самое, что восстановление полного отношения эквивалентности по его части.

Альтернативные определения моста:

• ребро является мостом, если не участвует ни в одном цикле;
• ребро [math]e[/math] является мостом, если существует пара вершин [math](u, v)[/math] из одной компоненты связности, любой путь [math]P(u, v)[/math] между которыми проходит через ребро [math]e[/math].

Шарнир разделяет компоненты двусвязности (если две компоненты двусвязности имеют общую вершину, то это шарнир).

Каждая из вершин моста является шарниром (кроме случая, когда мост является единственным ребром этой вершины).

Компонента сильной связности является объединением всех циклом, проходящих через её вершины.

6.3 Алгоритмы

Компоненты связности могут быть найдены:

• последовательным применением алгоритма поиска в ширину за время [math]O(m)[/math];
• с помощью системы непересекающихся множеств за время [math]O(m \alpha(m, n))[/math], с возможностью эффективной многопоточной реализации;
• параллельным алгоритмом Шилоаха-Вишкина за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.

Компоненты сильной связности могут быть найдены:

• алгоритмом Тарьяна (в ходе поиска в глубину) за время [math]O(m)[/math];
• параллельным алгоритмом DCSC с работой [math]O(n \ln n)[/math].

Мосты могут быть найдены:

• алгоритмом Тарьяна (в ходе поиска в глубину) за время [math]O(m)[/math];
• параллельным алгоритмом Тарьяна-Вишкина за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах;
• онлайн-алгоритмом Уэстбрука-Тарьяна за время [math]O(m \alpha(m, n))[/math].

Компоненты двусвязности могут быть найдены:

• алгоритмом Тарьяна (в ходе поиска в глубину) за время [math]O(m)[/math] (алгоритм также находит и соответствующие шарниры);
• параллельным алгоритмом Тарьяна-Вишкина за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах (алгоритм также может находить и мосты);
• онлайн-алгоритмом Уэстбрука-Тарьяна за время [math]O(m \alpha(m, n))[/math].

Задача определения вершинной связности графа сводится к поиску максимальных потоков и может быть решена за время [math]O(\min\{k^3 + n, kn\} m)[/math].

Рёберная связность графа может быть найдена алгоритмом Габова за время [math]O(k m \ln (n^2/m))[/math] для ориентированного и [math]O(m + k^2 n \ln (n/k))[/math] неориентированного графа. Проверка свойства [math]k[/math]-связности тем же алгоритмом может быть выполнена за время [math]O(m + n \ln n)[/math].

7 Поиск максимального потока в транспортной сети

7.1 Постановка задачи

Транспортной сетью называется ориентированный граф [math]G = (V, E)[/math], каждому ребру [math]e \in E[/math] которого приписана неотрицательная пропускная способность [math]c(e) \ge 0[/math]. Будем считать, что вместе с каждым ребром [math]e = (v, w) \in E[/math] граф содержит и обратное к нему [math]e^R = (w, v)[/math] (при необходимости приписывая ему нулевую пропускную способность).

Пусть в графе [math]G[/math] выделены две вершины: источник [math]s[/math] и сток [math]t[/math]. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из [math]s[/math] в [math]t[/math]. Потоком называется функция [math]f: E \to \mathbb{R}[/math], удовлетворяющая следующим требованиям:

• ограничение по пропускной способности: [math]f(e) \le c(e)[/math];
• антисимметричность: [math]f(e^R) = -f(e)[/math];
• закон сохранения потока:

[math] \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). [/math]

Величиной потока называется суммарный поток из источника:

[math] \lvert f \rvert = \sum_{e = (s, v)} f(e). [/math]

Задача о максимальном потоке в транспортной сети. Требуется найти поток максимальной величины:

[math]\lvert f \rvert \to \max.[/math]

7.2 Свойства задачи

Суммарный поток из источника равен суммарному потоку в сток:

[math] \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). [/math]

(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

7.3 Варианты задачи

В зависимости от ограничений на значения пропускной способности:

• произвольная положительная пропускная способность;
• целая пропускная способность;
• единичная пропускная способность (в этом случае максимальный поток равен рёберной связности графа).

7.4 Алгоритмы решения задачи

• Алгоритм Форда-Фалкерсона и его варианты со сложностью [math]O(n^2m)[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]K[/math], сложность [math]O(Km)[/math].
• Алгоритм проталкивания предпотока со сложностью [math]O(mn \ln n)[/math] (при использовании динамических деревьев Тарьяна-Слитора).

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.

8 Задача о назначениях

8.1 Постановка задачи

Пусть имеется [math]n[/math] агентов и [math]m[/math] задач, которые могут быть распределены между этими агентами. Каждому агенту может быть выделена только одна задача, и каждая задача может быть выделена только одному агенту. Стоимость присвоения [math]i[/math]-й задачи [math]j[/math]-му агенту равна [math]c(i, j)[/math]. В случае [math]c(i, j) = \infty[/math] задача [math]j[/math] не может быть назначена агенту [math]i[/math].

Задача о назначениях: сформировать допустимое множество назначений [math]A = \{ (i_1, j_1), \ldots, (i_k, j_k) \}[/math], [math]k = \min \{m, n\}[/math], имеющее макисмальную суммарную стоимость:

[math] C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max. [/math]

8.2 Варианты задачи

При [math]m = n[/math] задача называется линейной: каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.

В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.

8.3 Алгоритмы решения задачи

• Венгерский алгоритм для линейной задачи, сложность [math]O(n^4)[/math] (может быть уменьшена до [math]O(n^3)[/math]);
• Алгоритм аукциона;
• Алгоритм Гопкрофта-Карпа для задачи с единичными ценами, сложность [math]O(m \sqrt{n})[/math].

Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.

Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.

Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.

Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.

Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.

Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.

Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.

Djidjev, Hristo N, Grammati E Pantziou, and Christos D Zaroliagis. “On-Line and Dynamic Algorithms for Shortest Path Problems.” In Proceedings of STACS 95, 193–204. Lecture Notes in Computer Science Vol. 900, Berlin, Heidelberg: Springer, 1995. doi:10.1007/3-540-59042-0_73.

Demetrescu, Camil, and Giuseppe F Italiano. “Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.” Journal of Computer and System Sciences 72, no. 5 (August 2006): 813–37. doi:10.1016/j.jcss.2005.05.005.

Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.

Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.

Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.

Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.

Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.

Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.

Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.

Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.

Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.

Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.

Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.

Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.

Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.

Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.

Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.

Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.

Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.

Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.

Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.

Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.

Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.

Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (January 1956): 48–50. doi:10.1090/S0002-9939-1956-0078686-7.

Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.

Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.

Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.

Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.

Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.

Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.

Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.

Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.

Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.

Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.

Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.

Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.

Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.

Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.

Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.

McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.

Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.

Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.

Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

Westbrook, Jeffery, and Robert Endre Tarjan. “Maintaining Bridge-Connected and Biconnected Components on-Line.” Algorithmica 7, no. 1 (June 1992): 433–64. doi:10.1007/BF01758773.

Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

Henzinger, Monika R, Satish Rao, and Harold N Gabow. “Computing Vertex Connectivity: New Bounds From Old Techniques.” Journal of Algorithms 34, no. 2 (February 2000): 222–50. doi:10.1006/jagm.1999.1055.

Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.

Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.

Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.

Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.

Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.

Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.

Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.

Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.

Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.

Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.

Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.

Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.

Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.

Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.