Вершинно k-связный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
4-связный граф: при удалении любых трёх вершин, он остаётся связным.

В теории графов говорят, что нетривиальный граф 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-вершинно-связный планарный граф образует скелет выпуклого многогранника.

Примечания

[править | править код]
  1. 1 2 Schrijver. Combinatorial Optimization. — Springer.

Литература

[править | править код]
  • 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.