k -связный граф - k-vertex-connected graph

График со связностью 4.

В теории графов , A связной граф G называется к -vertex соединенному (или к связному ) , если она имеет более , чем K вершина и остатки соединены всякий раз , когда меньше , чем к вершинам удаляются.

Вершина-подключение , или просто связность , графа является самым большим к , для которого граф к -vertex-подключено.

Определения

Граф (кроме полного ) имеет связность k, если k - размер наименьшего подмножества вершин, так что граф становится несвязным, если вы их удалите. Полные графы не включены в эту версию определения, поскольку их нельзя разъединить, удалив вершины. Полный граф с n вершинами имеет связность n  - 1, как следует из первого определения.

Эквивалентное определение состоит в том, что граф, по крайней мере, с двумя вершинами, является k -связным, если для каждой пары его вершин можно найти k независимых от вершин путей, соединяющих эти вершины; см . теорему Менгера ( Diestel 2005 , p. 55). Это определение дает тот же ответ, n  - 1, для связности полного графа K _n .

Односвязный граф называется связным ; двусвязный граф называется двусвязным . Трехсвязный граф называется трехсвязным.

Приложения

Многогранная комбинаторика

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

Вычислительная сложность

Связность по вершинам входного графа G может быть вычислена за полиномиальное время следующим образом: рассмотрим все возможные пары несмежных узлов для разъединения, используя теорему Менгера, чтобы обосновать, что разделитель минимального размера для - это количество попарно независимых от вершин путей. между ними, кодируйте вход, удваивая каждую вершину как ребро, чтобы уменьшить количество попарно независимых от ребер путей, и вычислите максимальное количество таких путей, вычислив максимальный поток в графе между и с пропускной способностью от 1 до каждое ребро, отмечая, что поток из в этом графе соответствует, по теореме об интегральном потоке , попарно независимым от ребер путям от до . ${\ displaystyle (s, t)}$${\ displaystyle (s, t)}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle s}$${\ displaystyle t}$

Смотрите также

• k- реберный граф
• Связность (теория графов)
• Теорема Менгера
• Структурная сплоченность
• Вложение Тутте
• Разделитель вершин

Примечания

Ссылки

• Балински, М.Л. (1961), "О структуре графа выпуклых многогранников в n- пространстве", Тихоокеанский математический журнал , 11 (2): 431–434, DOI : 10.2140 / pjm.1961.11.431.
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4.