граф с связностью k вершин

Граф, который остается связным при удалении k или менее узлов

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

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

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

Определения

Граф (кроме полного графа ) имеет связность k , если k — размер наименьшего подмножества вершин, при удалении которых граф становится несвязным. ^[1] В полных графах нет подмножества, удаление которого сделало бы граф несвязным. Некоторые источники изменяют определение связности, чтобы справиться с этим случаем, определяя его как размер наименьшего подмножества вершин, удаление которых приводит либо к несвязному графу, либо к одной вершине. Для этого варианта связность полного графа равна . ^[2] ${\displaystyle K_{n}}$ ${\displaystyle n-1}$

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

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

Приложения

Компоненты

Каждый граф распадается на несвязное объединение 1-связных компонент . 1-связные графы распадаются на дерево двусвязных компонент . 2-связные графы распадаются на дерево трисвязных компонент .

Полиэдральная комбинаторика

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

Сложность вычислений

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

Характеристики

Пусть k≥2 .

• Каждый -связный граф порядка не менее содержит цикл длины не менее ${\displaystyle k}$ ${\displaystyle 2k}$ ${\displaystyle 2k}$
• В -связном графе любые вершины лежат на общем цикле . ^[5] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$

Пространство циклов -связного графа генерируется его неразделяющими индуцированными циклами . ^[6] ${\displaystyle 3}$

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

Граф с по крайней мере вершинами называется -связанным, если существуют непересекающиеся пути для любых последовательностей и различных вершин. Каждый -связанный граф является -связанным графом, но не обязательно -связанным. ^[7] ${\displaystyle 2k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\displaystyle b_{1},\dots ,b_{k}}$ ${\displaystyle 2k}$ ${\displaystyle k}$ ${\displaystyle (2k-1)}$ ${\displaystyle 2k}$

Если граф -связан и имеет среднюю степень не менее , то он -связан. ^[8] ${\displaystyle 2k}$ ${\displaystyle 16k}$ ${\displaystyle k}$

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

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

Примечания

1. Schrijver (12 февраля 2003 г.), Комбинаторная оптимизация, Springer, ISBN 9783540443896
2. Бейнеке, Лоуэлл В.; Багга, Джей С. (2021), Линейные графы и линейные орграфы, Развитие математики, т. 68, Springer Nature, стр. 87, ISBN 9783030813864
3. Балински, М. Л. (1961), «О структуре графа выпуклых многогранников в n -пространстве», Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140/pjm.1961.11.431.
4. Руководство по разработке алгоритмов , стр. 506, и Вычислительная дискретная математика: комбинаторика и теория графов с Mathematica , стр. 290-291
5. Дистель (2016), стр.84
6. Дистель (2012), стр.65.
7. Дистель (2016), стр.85
8. Дистель (2016), стр.75

Ссылки

• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4
• Дистель, Рейнхард (2012), Теория графов (исправленное 4-е электронное издание)
• Дистель, Рейнхард (2016), Теория графов (5-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-662-53621-6