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

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

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

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

Определения [ править ]

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

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

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

Приложения [ править ]

Многогранная комбинаторика [ править ]

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

Вычислительная сложность [ править ]

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

См. Также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

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

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

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

[1]