Вершинно 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-скелет[en] любого k-мерного выпуклого многогранника образует k-вершинно-связный граф (Теорема Балинского[en], Balinski 1961). Частично обратная теорема Штейница[en] утверждает, что любой 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. — В. 2. — Т. 11. — С. 431–434..
  • Reinhard Diestel Graph Theory. — 3rd. — Berlin, New York: Springer-Verlag, 2005. — ISBN 978-3-540-26183-4..