stringtranslate.com

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

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

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

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

Определения

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

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

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

Приложения

Компоненты

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

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

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

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

Связность вершин входного графа G можно вычислить за полиномиальное время следующим образом [4]: ​​рассмотрим все возможные пары несмежных узлов для разъединения, используя теорему Менгера для обоснования того, что минимальный размер разделителя для равен числу попарно независимых вершин путей между ними, закодируем входные данные, удвоив каждую вершину как ребро, чтобы свести вычисление к числу попарно независимых ребер путей, и вычислим максимальное число таких путей, вычислив максимальный поток в графе между и с пропускной способностью 1 для каждого ребра, отметив, что поток в этом графе соответствует, по теореме об интегральном потоке , попарно независимым от ребер путям от до .

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

Пусть k≥2 .

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

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

Граф с по крайней мере вершинами называется -связанным, если существуют непересекающиеся пути для любых последовательностей и различных вершин. Каждый -связанный граф является -связанным графом, но не обязательно -связанным. [7]

Если граф -связан и имеет среднюю степень не менее , то он -связан. [8]

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

Примечания

  1. ^ ab 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

Ссылки