Оглавление
K-вершинно-связный граф
-
Определение связности графа
- Граф G называется k-вершинно-связным, если удаление менее k вершин не нарушает его связность.
- Связность графа – это наибольшее k, при котором граф остается k-вершинно-связным.
-
Эквивалентные определения
- Граф с двумя или более вершинами является k-связным, если существует k независимых путей между каждой парой вершин.
- Полный граф Kn имеет связность n − 1 согласно этому определению.
-
Приложения связности
- Графы могут быть разложены на деревья из односвязных, двусвязных и трехсвязных компонентов.
- Теорема Балинского утверждает, что 1-скелет выпуклого многогранника является k-вершинно-связным графом.
-
Вычислительная сложность
- Вершинная связность графа может быть вычислена за полиномиальное время, используя теорему Менгера и методы теории графов.
-
Свойства k-связных графов
- Каждый k-связный граф содержит цикл длиной не менее 2k.
- k-связный граф имеет k непересекающихся путей для любых последовательностей вершин.
- k-связанный граф является (2k − 1)-связным, но не обязательно 2k-связным.
- Если граф 2k-связан и имеет среднюю степень не менее 16k, то он k-связан.
Полный текст статьи: