В теории графов говорят, что нетривиальный граф G вершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.
Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен.
Альтернативно граф, отличный от полного, имеет связность k, если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным[1]. Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения.
Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера (Diestel 2005, С. 55). Это определение имеет тот же ответ: n − 1 для связности полного графа Kn[1].
1-связный граф называется также связным, 2-связный граф называется двусвязным, 3-связный граф называется, соответственно, трисвязным.
1-скелет любого k-мерного выпуклого многогранника образует k-вершинно-связный граф (Теорема Балинского, Balinski, 1961). Частично обратная теорема Штейница утверждает, что любой 3-вершинно-связный планарный граф образует скелет выпуклого многогранника.
Энциклопедичный YouTube
-
1/3Просмотров:2 5527753 753
-
Связность графов
-
Алгоритмы и структуры данных 4. Графы
-
Episode 22 - Biconnected Decompositions
Субтитры
См. также
Примечания
Литература
- M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — Т. 11, вып. 2. — С. 431—434.
- Reinhard Diestel. Graph Theory. — 3rd. — Berlin, New York: Springer—Verlag, 2005. — ISBN 978-3-540-26183-4.
Эта страница в последний раз была отредактирована 10 июня 2021 в 11:18.
Обычно почти сразу, изредка в течении часа.