Связность в графах - История изменений

ASA в 14:03, 6 марта 2018

2018-03-06T14:03:33Z

← Предыдущая версия		Версия от 14:03, 6 марта 2018
Строка 1:		Строка 1:
			{{level-p}}

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

ASA в 11:20, 29 июля 2015

2015-07-29T11:20:24Z

← Предыдущая версия		Версия от 11:20, 29 июля 2015
Строка 69:		Строка 69:

	<references />		<references />

			[[Категория:Статьи в работе]]

Daryin: /* Алгоритмы */

2015-06-06T19:44:27Z

Алгоритмы

← Предыдущая версия		Версия от 19:44, 6 июня 2015
Строка 54:		Строка 54:
	Мосты могут быть найдены:		Мосты могут быть найдены:
	* [[Алгоритм Тарьяна поиска «мостов» в графе\|алгоритмом Тарьяна]]<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> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>;		* [[Алгоритм Тарьяна поиска «мостов» в графе\|алгоритмом Тарьяна]]<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> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>;
	* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;		* параллельным [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;
	* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>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.</ref> за время <math>O(m \alpha(m, n))</math>.		* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>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.</ref> за время <math>O(m \alpha(m, n))</math>.

	Компоненты двусвязности могут быть найдены:		Компоненты двусвязности могут быть найдены:
	* [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);		* [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);
	* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах (алгоритм также может находить и мосты);		* параллельным [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах (алгоритм также может находить и мосты);
	* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.		* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.

Daryin: /* Алгоритмы */

2015-06-05T12:55:35Z

Алгоритмы

← Предыдущая версия		Версия от 12:55, 5 июня 2015
Строка 54:		Строка 54:
	Мосты могут быть найдены:		Мосты могут быть найдены:
	* [[Алгоритм Тарьяна поиска «мостов» в графе\|алгоритмом Тарьяна]]<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> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>;		* [[Алгоритм Тарьяна поиска «мостов» в графе\|алгоритмом Тарьяна]]<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> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>;
			* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;
	* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>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.</ref> за время <math>O(m \alpha(m, n))</math>.		* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>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.</ref> за время <math>O(m \alpha(m, n))</math>.

	Компоненты двусвязности могут быть найдены:		Компоненты двусвязности могут быть найдены:
	* [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);		* [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);
	* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;		* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах (алгоритм также может находить и мосты);
	* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.		* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.

Daryin: /* Алгоритмы */

2015-06-05T12:39:26Z

Алгоритмы

← Предыдущая версия		Версия от 12:39, 5 июня 2015
Строка 49:		Строка 49:

	Компоненты сильной связности могут быть найдены:		Компоненты сильной связности могут быть найдены:
	* [[Алгоритм Тарьяна поиска компонент сильной связности\|алгоритмом Тарьяна]]<ref name=DFS>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math> ~~(алгоритм также находит и соответствующие шарниры)~~;		* [[Алгоритм Тарьяна поиска компонент сильной связности\|алгоритмом Тарьяна]]<ref name=DFS>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (в ходе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>;
	* [[Алгоритм DCSC поиска компонент сильной связности\|параллельным алгоритмом DCSC]]<ref>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.</ref><ref>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.</ref><ref>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.</ref> с работой <math>O(n \ln n)</math>.		* [[Алгоритм DCSC поиска компонент сильной связности\|параллельным алгоритмом DCSC]]<ref>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.</ref><ref>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.</ref><ref>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.</ref> с работой <math>O(n \ln n)</math>.

Daryin: /* Алгоритмы */

2015-06-05T12:33:27Z

Алгоритмы

← Предыдущая версия		Версия от 12:33, 5 июня 2015
Строка 45:		Строка 45:
	Компоненты связности могут быть найдены:		Компоненты связности могут быть найдены:
	* последовательным применением алгоритма [[Поиск в ширину (BFS)\|поиска в ширину]] за время <math>O(m)</math>;		* последовательным применением алгоритма [[Поиск в ширину (BFS)\|поиска в ширину]] за время <math>O(m)</math>;
	* с помощью [[Система непересекающихся множеств\|системы непересекающихся множеств]]<ref>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.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>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.</ref>		* с помощью [[Система непересекающихся множеств\|системы непересекающихся множеств]]<ref>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.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>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.</ref>;
	* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности\|Шилоаха-Вишкина]]<ref>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.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.		* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности\|Шилоаха-Вишкина]]<ref>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.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.

Daryin: Новая страница: «== Основные определения == Пусть задан (ориентированный или неориентированный) граф $G =…»$

2015-06-02T12:07:37Z

Новая страница: «== Основные определения == Пусть задан (ориентированный или неориентированный) граф <math>G =…»

Новая страница

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

Пусть задан (ориентированный или неориентированный) граф <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> называется ''рёберной связностью'' графа.

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

== Свойства ==

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

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

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

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

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

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

== Алгоритмы ==

Компоненты связности могут быть найдены:
* последовательным применением алгоритма [[Поиск в ширину (BFS)|поиска в ширину]] за время <math>O(m)</math>;
* с помощью [[Система непересекающихся множеств|системы непересекающихся множеств]]<ref>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.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>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.</ref>
* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности|Шилоаха-Вишкина]]<ref>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.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.

Компоненты сильной связности могут быть найдены:
* [[Алгоритм Тарьяна поиска компонент сильной связности|алгоритмом Тарьяна]]<ref name=DFS>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);
* [[Алгоритм DCSC поиска компонент сильной связности|параллельным алгоритмом DCSC]]<ref>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.</ref><ref>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.</ref><ref>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.</ref> с работой <math>O(n \ln n)</math>.

Мосты могут быть найдены:
* [[Алгоритм Тарьяна поиска «мостов» в графе|алгоритмом Тарьяна]]<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> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math>;
* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan>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.</ref> за время <math>O(m \alpha(m, n))</math>.

Компоненты двусвязности могут быть найдены:
* [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритмом Тарьяна]]<ref name=DFS /> (в ходе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math> (алгоритм также находит и соответствующие шарниры);
* параллельным [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> за время <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах;
* онлайн-алгоритмом Уэстбрука-Тарьяна<ref name=WestbrookTarjan /> за время <math>O(m \alpha(m, n))</math>.

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

Рёберная связность графа может быть найдена [[Алгоритм Габова определения рёберной связности графа|алгоритмом Габова]]<ref>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.</ref> за время <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>.

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

<references />

Связность в графах - История изменений

ASA в 14:03, 6 марта 2018

ASA в 11:20, 29 июля 2015

Daryin: /* Алгоритмы */

Daryin: /* Алгоритмы */

Daryin: /* Алгоритмы */

Daryin: /* Алгоритмы */

Daryin: Новая страница: «== Основные определения == Пусть задан (ориентированный или неориентированный) граф G =…»

Daryin: Новая страница: «== Основные определения == Пусть задан (ориентированный или неориентированный) граф $G =…»$