Алгоритм Крускала

2015-07-08T12:40:54Z

Daryin: /* Общее описание алгоритма */

Алгоритм Тарьяна поиска «мостов» в графе

2015-07-07T09:30:20Z

Daryin: /* Описание ресурса параллелизма алгоритма */

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Тарьяна''' <ref>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.</ref> находит [[Связность в графах|мосты]] в неориентированном графе за время <math>O(m)</math>.

=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===

Последовательная сложность алгоритма составляет <math>O(m)</math>.

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===

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

Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />

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

2015-07-07T09:13:46Z

Daryin: /* Постановка задачи */

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

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

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

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

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

'''[[Алгоритм Ульмана]]'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>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.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
* для фиксированного графа <math>H</math> время полиномиальное;
* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).

'''[[Алгоритм VF2]]'''<ref>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.</ref> разработан специально для применения на больших графах.

== Литература ==

<references />

Алгоритм Джонсона

2015-06-30T20:03:55Z

Daryin: /* Существующие реализации алгоритма */

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Джонсона'''<ref>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.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(mn + n^2 \ln n)</math>.

В случае разреженных графов алгоритм Джонсона эффективнее [[Алгоритм Флойда-Уоршелла|алгоритма Флойда-Уоршела]], имеющего сложность <math>O(n^3)</math>. Он применим к в случае произвольных (в том числе отрицательных) вещественных весов, в отличие от [[алгоритм Дейкстры]], имеющего ту же сложность.

=== Математическое описание ===

Алгоритм Джонсона использует [[алгоритм Беллмана-Форда]] для предварительной обработки графа, заменяя веса рёбер на неотрицательные. Далее к получившемуся графу многократно применяется [[алгоритм Дейкстры]].

=== Вычислительное ядро алгоритма ===

Основными вычислительными блоками алгоритма Джонсона являются [[алгоритм Беллмана-Форда]] и [[алгоритм Дейкстры]].

=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===

На этапе предварительной обработки выполняется алгоритм Беллмана-Форда сложностью <math>O(mn)</math>. Далее для каждой вершины графа выполняется алгоритм Дейкстры сложностью <math>O(m + n \ln n)</math>. Итоговая сложность алгоритма Джонсона <math>O(mn + n^2 \ln n)</math>.

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===

Алгоритм Джонсона может быть эффективно распараллелен, так как применение алгоритма Дейкстры для каждой вершины производится независимо. Кроме того, вместо алгоритма Дейкстры можно использовать параллельный [[алгоритм Δ-шагания]].

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html johnson_all_pairs_shortest_paths]</code>).

== Литература ==

<references />

2015-06-25T14:07:06Z

Алгоритм Гопкрофта-Карпа

2015-06-25T11:26:09Z

Daryin: /* Макроструктура алгоритма */

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Гопкрофта-Карпа'''<ref>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.</ref> предназначен для решения [[Задача о назначениях|задачи о назначениях]] в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время <math>O(m \sqrt{n})</math>.

=== Математическое описание ===
Граф <math>G = (V, E)</math> называется ''двудольным'', если его вершины можно разделить на две части <math>V = X \sqcup Y</math>, так что каждое ребро <math>e \in E</math> соединяет вершины из <math>X</math> и <math>Y</math>. Набор рёбер <math>M \subseteq E</math> называется ''паросочетанием'', если каждая вершина <math>v \in V</math> принадлежит не более чем одному ребру из <math>M</math>. Требуется найти '''максимальное паросочетание''' – паросочетание с максимально возможным числом рёбер.

Вершина <math>v \in V</math> называется свободной, если она не принадлежит ни одному ребру из <math>M</math>. Простой путь
:<math>
P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k})
</math>
называется ''увеличивающей цепью'', если его концы <math>v_1</math> и <math>v_{2k}</math> – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:
:<math>
e_2, e_4, \ldots, e_{2k-2} \in M.
</math>
Паросочетание <math>M</math> является максимальным, если для него не существует увеличивающей цепи.

Множество <math>M'</math>, полученное заменой в <math>M</math> рёбер <math>e_2, e_4, \ldots, e_{2k-2}</math> на рёбра <math>e_1, e_3, \ldots, e_{2k-1}</math>, является паросочетанием и содержит на одно ребро больше, чем <math>M</math>. Множество <math>M' = M \mathop{\Delta} P</math>, где <math>\mathop{\Delta}</math> обозначает операцию симметрической разности множеств.

На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей <math>\{ P_1, \ldots, P_q \}</math>, не пересекающихся по вершинам, и текущее паросочетание <math>M</math> заменяется на <math>M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math>. Гарантируется, что число шагов не превышает <math>2 (\sqrt{\mu} + 1) = O(\sqrt{n})</math>, где <math>\mu</math> – число рёбер максимального паросочетания.

Для поиска максимального множества кратчайших увеличивающих цепей применяется [[Поиск в ширину (BFS)|поиск в ширину]] с последующим [[Поиск в глубину (DFS)|поиском в глубину]].

=== Вычислительное ядро алгоритма ===
Основная вычислительная сложность алгоритма приходится на операции [[Поиск в ширину (BFS)|поиска в ширину]] и [[Поиск в глубину (DFS)|поиска в глубину]].

=== Макроструктура алгоритма ===

# Выбрать начальное паросочетание <math>M_0</math> (например, <math>M_0 = \emptyset</math> или паросочетание, полученное жадным алгоритмом).
# Вычислить максимальное по включение множество кратчайших увеличивающих цепей <math>\{ P_1, \ldots, P_q \}</math>, не пересекающихся по вершинам. Если улучшающих цепей не существует, остановиться: текущее паросочетание <math>M_i</math> является максимальным.
# Составить новое паросочетание <math>M_{i + 1} = M_i \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math> и перейти к шагу 2.

=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
Алгоритм выполняет не более <math>O(\sqrt{n})</math> шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью <math>O(m)</math>. Таким образом, общая сложность составляет <math>O(m \sqrt{n})</math>.

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/HopcroftKarpBipartiteMatching.html HopcroftKarpBipartiteMatching]</code>).

== Литература ==

<references />