k -вершинно-связный граф

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

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

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

Определения

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

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

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

Приложения

Компоненты

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

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

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

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

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

Свойства

Пусть k≥2 .

• Каждый $k$-связный граф порядка не менее $2k$ содержит цикл длины не менее $2k$
• В $k$-связный граф, любой $k$ вершины в $G$ лежат в общем цикле .

цикла Пространство a $3$-связный граф порождается своими неразделяющими индуцированными циклами .

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

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

Если график $2k$-связен и имеет среднюю степень не ниже $16k$, тогда это $k$-связанный.

См. также

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

Ссылки

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