Связность (теория графов)

Этот граф становится несвязным, когда пунктирное ребро удаляется.

В математике и информатике количества элементов (узлов или ребер) , связность — одно из основных понятий теории графов : она требует минимального которые необходимо удалить, чтобы разделить оставшиеся узлы на два или более изолированных подграфа . ^[1] Это тесно связано с теорией задач сетевых потоков . Связность графа является важной мерой его устойчивости как сети.

Связные вершины и графы

С вершиной 0 этот граф несвязен. Остальная часть графа связна.

В неориентированном графе $G$ две вершины $u$ и $v$ называются связными , если $G$ содержит путь из $u$ в $v$ . В противном случае их называют отключенными . Если две вершины дополнительно соединены путем длиной $1$ (т. е. являются концами одного ребра), такие вершины называются смежными .

Граф если называется связным, каждая пара вершин графа связна. существует путь Это означает, что между каждой парой вершин . Неориентированный граф, который не является связным, называется несвязным . Таким образом, неориентированный граф $G$ является несвязным, если существуют две вершины в $G$ такие, что ни один путь в $G$ не имеет этих вершин в качестве концов. Граф, имеющий всего одну вершину, связен. Граф без ребер с двумя и более вершинами является несвязным.

называется Ориентированный граф слабосвязным , если замена всех его ориентированных ребер неориентированными дает связный (неориентированный) граф. Он односторонне связный или односторонний (также называемый полусвязным ), если он содержит направленный путь от $u$ до $v$ или направленный путь от $v$ до $u$ для каждой пары вершин $u, v$ . ^[2] Оно сильно связное или просто сильное, если оно содержит направленный путь от $u$ до $v$ и направленный путь от $v$ до $u$ для каждой пары вершин $u, v$ .

Компоненты и разрезы

Компонент связности — это максимальный связный подграф неориентированного графа. Каждая вершина принадлежит ровно одному компоненту связности, как и каждое ребро. Граф связен тогда и только тогда, когда он имеет ровно одну компоненту связности.

Сильные компоненты — это максимальные сильно связные подграфы ориентированного графа.

или Разрез вершин разделяющее множество связного графа $G$ — это набор вершин, удаление которых делает $G$ несвязным. Связность вершин $κ (G)$ (где $G$ не полный граф ) — это размер минимального разреза вершин. Граф называется $k$ -вершинно-связным или $k$ -связным , если его связность вершин равна $k$ или больше.

Точнее, любой граф $G$ (полный или нет) называется $k$ -вершинно связным , если он содержит не менее $k + 1$ вершины, но не содержит набора из $k - 1$ вершин, удаление которых разъединяет граф; и $κ (G)$ определяется как наибольшее $k$ такое, что $k$ G $-$ связна. В частности, полный граф с $n$ вершинами, обозначаемый $K n$ , вообще не имеет разрезов вершин, но $κ (K n) = n - 1$ .

Вершинный разрез для двух вершин $u$ и $v$ — это набор вершин, удаление которых из графа разъединяет $u$ и $v$ . Локальная связность $κ (u, v)$ — это размер наименьшего разреза вершины, разделяющего $u$ и $v$ . Локальная связность симметрична для неориентированных графов; то есть $κ (ты, v) знак равно κ (v, ты)$ . Более того, за исключением полных графов, $κ (G)$ равно минимуму $κ (u, v)$ по всем несмежным парам вершин $u, v$ .

$2$ -связность также называется двусвязностью , а $3$ -связность также называется трисвязностью . Граф $G$ , который связен, но не $2$ -связен, иногда называют сепарабельным .

Аналогичные понятия можно определить для ребер. В простом случае, когда разрезание одного конкретного ребра приводит к отключению графа, это ребро называется мостом . В более общем смысле, разрез ребер $G$ — это набор ребер, удаление которых делает граф несвязным. Связность ребра $λ (G)$ — это размер наименьшего разреза ребра, а локальная связность ребра $λ (u, v)$ двух вершин $u, v$ — это размер наименьшего разреза ребра, отделяющего $u$ от $v$ . Опять же, локальная связность ребер симметрична. Граф называется $k$ -реберно-связным, если его связность ребер равна $k$ или больше.

Граф называется максимально связным, если его связность равна минимальной степени . Граф называется максимально связным по ребрам , если его связность по ребрам равна минимальной степени. ^[3]

Супер- и гиперсвязность

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

Точнее: $связный граф G$ называется сверхсвязным или супер-κ, если все минимальные вершины-разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). Связный граф $G$ называется суперсвязным или супер-λ, если все минимальные ребра состоят из ребер, инцидентных некоторой вершине (минимальной степени). ^[5]

Разрез $X$ группы $G$ называется нетривиальным разрезом, если $X$ не содержит окрестность $N(u)$ ни одной вершины $u \notin X$ . Тогда сверхсвязность $\kappa _{1}$ G $$ $\kappa _{1}(G)=\min\{|X|:X{\text{ is a non-trivial cutset}}\}.$

Нетривиальный разрез ребер и реберная сверхсвязность $\lambda _{1}(G)$ определяются аналогично. ^[6]

Теорема Менгера

Одним из наиболее важных фактов о связности в графах является теорема Менгера , которая характеризует связность и связность ребер графа с точки зрения количества независимых путей между вершинами.

Если $u$ и $v$ — вершины графа $G$ , то набор путей между $u$ и $v$ называется независимым, если никакие два из них не имеют общей вершины (кроме $самих u$ и $v$ ). Аналогично, коллекция не зависит от ребра, если никакие два пути в ней не имеют общего ребра. Количество взаимно независимых путей между $u$ и $v$ записывается как $κ'(u, v)$ , а количество взаимно независимых путей между $u$ и $v$ записывается как $λ' (u, v)$ .

Теорема Менгера утверждает, что для различных вершин u , v , $λ (u, v)$ равно $λ'(u, v)$ , а если u также не смежно с v, то $κ (u, v)$ равно $κ'(u, v)$ . ^[7]^[8] Этот факт на самом деле является частным случаем теоремы о максимальном потоке и минимальном сокращении .

Вычислительные аспекты

Проблему определения того, связаны ли две вершины в графе, можно эффективно решить с помощью алгоритма поиска , например поиска в ширину . В более общем смысле легко определить вычислительным путем, является ли граф связным (например, с помощью структуры данных с непересекающимся набором ), или подсчитать количество связанных компонентов. Простой алгоритм можно записать в псевдокоде следующим образом:

любого произвольного узла графа $G.$ Начните с
Продолжайте от этого узла, используя поиск в глубину или в ширину, подсчитывая все достигнутые узлы.
Если после полного обхода графа количество подсчитанных узлов равно количеству узлов $G$ , граф связен; в противном случае он отключен.

По теореме Менгера для любых двух вершин $u$ и $v$ в связном графе $G$ числа $κ (u, v)$ и $λ (u, v)$ могут быть эффективно определены с использованием алгоритма min-cut с максимальным потоком . Связность и связность ребер $G$ затем можно вычислить как минимальные значения $κ (u, v)$ и $λ (u, v)$ соответственно.

В сложности вычислений теории SL — это класс задач лог-пространства, сводимый проблеме определения того, связаны ли две вершины в графе, равенство которой было доказано Омером к Рейнгольдом в 2004 году. ^[9] Следовательно, связность неориентированного графа может быть решена в $O(log n)$ пространстве .

Проблема вычисления вероятности того, что случайный граф Бернулли связен, называется надежностью сети, а проблема вычисления того, связаны ли две заданные вершины, - проблемой ST-надежности. Оба из них #P -трудны. ^[10]

Количество связанных графов

Количество различных связных помеченных графов с n узлами сведено в таблицу в Электронной энциклопедии целочисленных последовательностей как последовательность A001187 . Первые несколько нетривиальных терминов:

н	графики
1	1
2	1
3	4
4	38
5	728
6	26704
7	1866256
8	251548592

Примеры

Связности вершин и ребер несвязного графа равны $0$ .
$1$ -связность эквивалентна связности графов, состоящих не менее чем из двух вершин.
Полный граф на $n$ вершинах имеет связность ребер, равную $n - 1$ . Любой другой простой граф с $n$ вершинами имеет строго меньшую связность ребер.
В дереве локальная связность ребер между любыми двумя различными вершинами равна $1$ .

Ограничения на подключение

Связность вершин графа меньше или равна его связности ребер. То есть $κ (G) \leq λ (G)$ .
Связность ребер для графа с минимум двумя вершинами меньше или равна минимальной степени графа, поскольку удаление всех ребер, инцидентных вершине минимальной степени, отключит эту вершину от остальной части графа. ^[1]
Для вершинно-транзитивного графа степени $d$ имеем: $2(d + 1)/3 ⩽ κ (G) ⩽ λ (G) = d$ . ^[11]
Для вершинно-транзитивного графа степени $d \leq 4$ , или для любого (неориентированного) минимального графа Кэли степени $d$ , или для любого симметричного графа степени $d$ , оба вида связности равны: $κ (G) = λ (G) = д$ . ^[12]

Другие объекты недвижимости

Связность сохраняется гомоморфизмами графов .
Если $G$ связен, то и его линейный граф $L (G)$ также связен.
Граф $G$ является $2$ -реберно связным тогда и только тогда, когда он имеет сильно связную ориентацию.
Теорема Балинского утверждает, что многогранный граф ( $1$ - скелет ) $k$ -мерного выпуклого многогранника является $k-$ вершинно-связным графом. ^[13] Предыдущая теорема Стейница о том, что любой 3-связный плоский граф является многогранным графом ( теорема Стейница ), дает частичное обратное .
Согласно теореме Г. А. Дирака , если граф $k$ -связен при $k \geq 2$ , то для каждого набора из $k$ вершин графа существует цикл , проходящий через все вершины этого множества. ^[14]^[15] Обратное верно, когда $k = 2$ .

См. также

Ссылки

^ Jump up to: ^а ^б Дистель, Р. (2005). «Теория графов, электронное издание» . п. 12.
^ Глава 11: Орграфы: Принцип двойственности орграфов: Определение
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 335 . ISBN 978-1-58488-090-5 .
^ Лю, Цинхай; Чжан, Чжао (01 марта 2010 г.). «Существование и верхняя граница для двух типов ограниченной связности» . Дискретная прикладная математика . 158 (5): 516–521. дои : 10.1016/j.dam.2009.10.017 .
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 338 . ISBN 978-1-58488-090-5 .
^ Бальбуэна, Камино; Кармона, Анхелес (1 октября 2001 г.). «О связности и сверхсвязности двудольных орграфов и графов». Арс Комбинаторика . 61 : 3–22. CiteSeerX 10.1.1.101.1458 .
^ Гиббонс, А. (1985). Алгоритмическая теория графов . Издательство Кембриджского университета .
^ Нагамоти, Х.; Ибараки, Т. (2008). Алгоритмические аспекты связности графов . Издательство Кембриджского университета.
^ Рейнгольд, Омер (2008). «Ненаправленное соединение в пространстве журналов». Журнал АКМ . 55 (4): 1–24. дои : 10.1145/1391289.1391291 . S2CID 207168478 .
^ Прован, Дж. Скотт; Болл, Майкл О. (1983). «Сложность подсчета разрезов и вычисления вероятности связности графа». SIAM Journal по вычислительной технике . 12 (4): 777–788. дои : 10.1137/0212053 . МР 0721012 . .
^ Годсил, К. ; Ройл, Г. (2001). Алгебраическая теория графов . Спрингер Верлаг.
^ Бабай, Л. (1996). Группы автоморфизмов, изоморфизм, реконструкция . Технический отчет ТР-94-10. Чикагский университет. Архивировано из оригинала 11 июня 2010 г. Глава 27 « Справочника по комбинаторике» .
^ Балинский, МЛ (1961). «О графическом строении выпуклых многогранников в $n$ -пространстве» . Тихоокеанский математический журнал . 11 (2): 431–434. дои : 10.2140/pjm.1961.11.431 .
^ Дирак, Габриэль Эндрю (1960). «Полные 4-графы, представленные в абстрактных графах и их подразделениях». Математические новости . 22 (1–2): 61–85. дои : 10.1002/mana.19600220107 . МР 0121311 . .
^ Фландрин, Эвелин; Ли, Хао; Марчик, Антони; Возняк, Мариуш (2007). «Обобщение теоремы Дирака о циклах по $k$ вершинам в $k$ -связных графах» . Дискретная математика . 307 (7–8): 878–884. дои : 10.1016/j.disc.2005.11.052 . МР 2297171 . .

[diestel-1] Jump up to: ^а ^б Дистель, Р. (2005). «Теория графов, электронное издание» . п. 12.

[2] Глава 11: Орграфы: Принцип двойственности орграфов: Определение

[3] Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 335 . ISBN 978-1-58488-090-5 .

[4] Лю, Цинхай; Чжан, Чжао (01 марта 2010 г.). «Существование и верхняя граница для двух типов ограниченной связности» . Дискретная прикладная математика . 158 (5): 516–521. дои : 10.1016/j.dam.2009.10.017 .

[5] Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 338 . ISBN 978-1-58488-090-5 .

[6] Бальбуэна, Камино; Кармона, Анхелес (1 октября 2001 г.). «О связности и сверхсвязности двудольных орграфов и графов». Арс Комбинаторика . 61 : 3–22. CiteSeerX 10.1.1.101.1458 .

[7] Гиббонс, А. (1985). Алгоритмическая теория графов . Издательство Кембриджского университета .

[8] Нагамоти, Х.; Ибараки, Т. (2008). Алгоритмические аспекты связности графов . Издательство Кембриджского университета.

[9] Рейнгольд, Омер (2008). «Ненаправленное соединение в пространстве журналов». Журнал АКМ . 55 (4): 1–24. дои : 10.1145/1391289.1391291 . S2CID 207168478 .

[10] Прован, Дж. Скотт; Болл, Майкл О. (1983). «Сложность подсчета разрезов и вычисления вероятности связности графа». SIAM Journal по вычислительной технике . 12 (4): 777–788. дои : 10.1137/0212053 . МР 0721012 . .

[GandR-11] Годсил, К. ; Ройл, Г. (2001). Алгебраическая теория графов . Спрингер Верлаг.

[12] Бабай, Л. (1996). Группы автоморфизмов, изоморфизм, реконструкция . Технический отчет ТР-94-10. Чикагский университет. Архивировано из оригинала 11 июня 2010 г. Глава 27 « Справочника по комбинаторике» .

[13] Балинский, МЛ (1961). «О графическом строении выпуклых многогранников в $n$ -пространстве» . Тихоокеанский математический журнал . 11 (2): 431–434. дои : 10.2140/pjm.1961.11.431 .

[14] Дирак, Габриэль Эндрю (1960). «Полные 4-графы, представленные в абстрактных графах и их подразделениях». Математические новости . 22 (1–2): 61–85. дои : 10.1002/mana.19600220107 . МР 0121311 . .

[15] Фландрин, Эвелин; Ли, Хао; Марчик, Антони; Возняк, Мариуш (2007). «Обобщение теоремы Дирака о циклах по $k$ вершинам в $k$ -связных графах» . Дискретная математика . 307 (7–8): 878–884. дои : 10.1016/j.disc.2005.11.052 . МР 2297171 . .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]