Связность в графах
Содержание
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] называется рёберной связностью графа.
Компонентой двусвязности графа называется максимальный по включению двусвязный подграф.
2 Свойства
Эквивалентные определения компоненты связности:
- все вершины, достижимые из какой-либо выбранной вершины;
- набор вершин, достижимых друг из друга, и не достижимых из других вершин.
Отношение «вершина [math]v[/math] достижима из вершины [math]u[/math]» является отношением эквивалентности. Таким образом, поиск связных компонент графа это то же самое, что восстановление полного отношения эквивалентности по его части.
Альтернативные определения моста:
- ребро является мостом, если не участвует ни в одном цикле;
- ребро [math]e[/math] является мостом, если существует пара вершин [math](u, v)[/math] из одной компоненты связности, любой путь [math]P(u, v)[/math] между которыми проходит через ребро [math]e[/math].
Шарнир разделяет компоненты двусвязности (если две компоненты двусвязности имеют общую вершину, то это шарнир).
Каждая из вершин моста является шарниром (кроме случая, когда мост является единственным ребром этой вершины).
Компонента сильной связности является объединением всех циклом, проходящих через её вершины.
3 Алгоритмы
Компоненты связности могут быть найдены:
- последовательным применением алгоритма поиска в ширину за время [math]O(m)[/math];
- с помощью системы непересекающихся множеств[1] за время [math]O(m \alpha(m, n))[/math], с возможностью эффективной многопоточной реализации[2];
- параллельным алгоритмом Шилоаха-Вишкина[3] за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.
Компоненты сильной связности могут быть найдены:
- алгоритмом Тарьяна[4] (в ходе поиска в глубину) за время [math]O(m)[/math];
- параллельным алгоритмом DCSC[5][6][7] с работой [math]O(n \ln n)[/math].
Мосты могут быть найдены:
- алгоритмом Тарьяна[8] (в ходе поиска в глубину) за время [math]O(m)[/math];
- параллельным алгоритмом Тарьяна-Вишкина[9] за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах;
- онлайн-алгоритмом Уэстбрука-Тарьяна[10] за время [math]O(m \alpha(m, n))[/math].
Компоненты двусвязности могут быть найдены:
- алгоритмом Тарьяна[4] (в ходе поиска в глубину) за время [math]O(m)[/math] (алгоритм также находит и соответствующие шарниры);
- параллельным алгоритмом Тарьяна-Вишкина[11] за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах (алгоритм также может находить и мосты);
- онлайн-алгоритмом Уэстбрука-Тарьяна[10] за время [math]O(m \alpha(m, n))[/math].
Задача определения вершинной связности графа сводится к поиску максимальных потоков и может быть решена за время [math]O(\min\{k^3 + n, kn\} m)[/math][12].
Рёберная связность графа может быть найдена алгоритмом Габова[13] за время [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].
4 Литература
- ↑ 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.
- ↑ 4,0 4,1 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.
- ↑ 10,0 10,1 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.
