Jump to content

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

(Перенаправлено из Vertex Connection )
Граф со связностью 4.

В теории графов связный граф 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]

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. Перейти обратно: Перейти обратно: а б Писатель (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
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8a328712c94437ccebd93186ad013b62__1718368860
URL1:https://arc.ask3.ru/arc/aa/8a/62/8a328712c94437ccebd93186ad013b62.html
Заголовок, (Title) документа по адресу, URL1:
k-vertex-connected graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)