K-вершинно-связный граф - K-vertex-connected graph

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

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

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

Определения

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

Эквивалентное определение состоит в том, что граф с как минимум двумя вершинами является k-связно, если для каждой пары его вершин можно найти k вершинно-независимый пути соединяя эти вершины; увидеть Теорема Менгера (Diestel 2005, п. 55). Это определение дает тот же ответ: п - 1, для связности полного графа K_п.^[1]

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

Приложения

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

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

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

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

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

Заметки

^ ^а ^б Шрайвер (12 февраля 2003 г.), Комбинаторная оптимизация, Спрингер, ISBN 9783540443896
^ Руководство по разработке алгоритмов, стр. 506, и Вычислительная дискретная математика: комбинаторика и теория графов в системе Mathematica, п. 290–291

использованная литература

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

[Schrijver-1] а ^б Шрайвер (12 февраля 2003 г.), Комбинаторная оптимизация, Спрингер, ISBN 9783540443896

[2] Руководство по разработке алгоритмов, стр. 506, и Вычислительная дискретная математика: комбинаторика и теория графов в системе Mathematica, п. 290–291

[1]

[2]