В теории графов говорят, что нетривиальный граф G вершинно k -связен (или k -связен ), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.

Вершинная связность , или просто связность , графа — это наибольшее k , для которого граф k -вершинно-связен.

Альтернативно граф, отличный от полного, имеет связность k , если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным . Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения.

Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера ( , С. 55). Это определение имеет тот же ответ: n − 1 для связности полного графа K _n .

1-связный граф называется также связным , 2-связный граф называется двусвязным , 3-связный граф называется, соответственно, трисвязным .

1- (англ.) ( любого k -мерного выпуклого многогранника образует k -вершинно-связный граф ( Теорема Балинского , ). Частично обратная теорема Штейница утверждает, что любой 3-вершинно-связный планарный граф образует скелет выпуклого многогранника .

См. также

• Рёберно k-связный граф
• Связный граф
• Теорема Менгера
• (англ.) (
• Вложение Татта

Примечания

Литература

• 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 .