k -вершинно-связный граф
В теории графов связный граф G называется k- вершинно-связным (или k -связным ), если он имеет более k вершин и остается связным менее k всякий раз, когда удаляется вершин.
Вершинная связность или просто связность графа — это наибольшее k , для которого граф является k -вершинно связным.
Определения
[ редактировать ]Граф (кроме полного графа ) имеет связность k , если k — размер наименьшего подмножества вершин, при котором граф становится несвязным, если вы их удаляете. [1] В полных графах не существует подмножества, удаление которого привело бы к отключению графа. Некоторые источники изменяют определение связности для обработки этого случая, определяя его как размер наименьшего подмножества вершин, удаление которых приводит либо к несвязному графу, либо к одной вершине. Для этого варианта связность полного графа является . [2]
Эквивалентное определение состоит в том, что граф, имеющий по крайней мере две вершины, является k -связным, если для каждой пары его вершин можно найти k независимых от вершин путей, соединяющих эти вершины; см. теорему Менгера ( Diestel 2005 , стр. 55). Это определение дает тот же ответ, n − 1, для связности полного графа K n . [1] Очевидно, что согласно этому определению полный граф с n вершинами имеет связность n − 1.
1-связный граф называется связным ; 2-связный граф называется двусвязным . Трехсвязный граф называется трехсвязным.
Приложения
[ редактировать ]Компоненты
[ редактировать ]Любой граф распадается на дерево 1-связных компонент . 1-связные графы разлагаются в дерево двусвязных компонент . 2-связные графы распадаются на дерево трехсвязных компонент .
Полиэдральная комбинаторика
[ редактировать ]1- остов любого k -мерного выпуклого многогранника образует k- вершинно-связный граф ( теорема Балинского ). [3] В качестве частичного обратного утверждения теорема Стейница связанный с 3 вершинами, утверждает, что любой планарный граф, образует скелет выпуклого многогранника .
Вычислительная сложность
[ редактировать ]Связность вершин входного графа G можно вычислить за полиномиальное время следующим образом: [4] рассмотреть все возможные пары несмежных узлов для разъединения, используя теорему Менгера , чтобы обосновать, что сепаратор минимального размера для - это количество попарных путей, независимых от вершин между ними, кодируйте входные данные, удваивая каждую вершину как ребро, чтобы свести к вычислению количества попарных путей, независимых от ребер, и вычисляйте максимальное количество таких путей путем вычисления максимального потока на графике между и с емкостью 1 на каждое ребро, учитывая, что поток на этом графике соответствует, по теореме об интегральном потоке , попарно независимые от ребер пути из к .
Характеристики
[ редактировать ]Пусть k≥2 .
- Каждый -связный граф порядка не менее содержит цикл длины не менее
- В -связный граф, любой вершины в лежат в общем цикле . [5]
цикла Пространство a -связный граф порождается своими неразделяющими индуцированными циклами . [6]
k- связанный граф
[ редактировать ]График, по крайней мере, вершин называется -связано, если есть непересекающиеся пути для любых последовательностей и из отдельные вершины. Каждый -связанный граф -связный граф, но не обязательно - связан. [7]
Если график -связен и имеет среднюю степень не ниже , тогда это -связанный. [8]
См. также
[ редактировать ]- k -реберно-связный граф
- Связность (теория графов)
- Теорема Менгера
- Структурная сплоченность
- Все встраивание
- Разделитель вершин
Примечания
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Писатель (12 февраля 2003 г.), Комбинаторная оптимизация , Springer, ISBN 9783540443896
- ^ Бейнеке, Лоуэлл В.; Багга, Джей С. (2021), Линейные графики и линейные орграфы , Развитие математики, том. 68, Springer Nature, с. 87, ISBN 9783030813864
- ^ Балинский, М.Л. (1961), «О графовой структуре выпуклых многогранников в n -пространстве», Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140/pjm.1961.11.431 .
- ^ Руководство по проектированию алгоритмов , стр. 506, и Вычислительная дискретная математика: комбинаторика и теория графов с Mathematica , стр. 290-291
- ^ Дистель (2016) , стр.84
- ^ Дистель (2012) , стр.65.
- ^ Дистель (2016) , стр.85
- ^ Дистель (2016) , стр.75
Ссылки
[ редактировать ]- Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4
- Дистель, Рейнхард (2012), Теория графов (исправленное 4-е электронное изд.)
- Дистель, Рейнхард (2016), Теория графов (5-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-662-53621-6