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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов говорят, что граф 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.