Связность (теория графов) - Connectivity (graph theory)
 | Было высказано предположение, что Мешулам игра быть слился в эту статью. (Обсудить) Предлагается с июля 2020 года. |
В математика и Информатика, возможность подключения одна из основных концепций теория графов: он просит минимум количество элементов (узлов или ребер), которые необходимо удалить, чтобы разделить оставшиеся узлы на изолированные подграфы.[1] Это тесно связано с теорией сетевой поток проблемы. Связность графа - важная мера его устойчивости как сети.
Связанные вершины и графы
В неориентированный граф г, два вершины ты и v называются связанный если г содержит дорожка от ты к v. В противном случае их называют отключен. Если две вершины дополнительно соединены путем длины 1, т.е. по одному ребру вершины называются смежный.
А график как говорят связанный если каждая пара вершин в графе связна. Это означает, что есть дорожка между каждой парой вершин. Несвязный неориентированный граф называется отключен. Неориентированный граф г поэтому отсоединяется, если существуют две вершины в г так что нет пути в г имеет эти вершины как конечные точки. Связен граф только с одной вершиной. An безграничный граф с двумя и более вершинами не связан.
А ориентированный граф называется слабо связанный если замена всех его ориентированных ребер на неориентированные дает связный (неориентированный) граф. это односторонне связанный или односторонний (также называемый полусоединенный), если он содержит направленный путь из ты к v или направленный путь от v к ты для каждой пары вершин u, v.[2] это сильно связанный, или просто сильный, если он содержит направленный путь от ты к v и направленный путь от v к ты для каждой пары вершин u, v.
Компоненты и разрезы
А связный компонент - максимальный связный подграф неориентированного графа. Каждая вершина принадлежит ровно одному компоненту связности, как и каждое ребро. Граф связен тогда и только тогда, когда он имеет ровно одну компоненту связности.
В сильные компоненты - максимальные сильно связные подграфы ориентированного графа.
А вершинный разрез или разделительный набор связного графа г - это набор вершин, удаление которых дает г отключен. В связность вершин κ(г) (где г это не полный график ) - размер минимального разреза вершины. Граф называется k-вершинно-связанный или k-связанный если связность его вершин k или выше.
Точнее любой граф г (полный или нет) называется k-вершинно-связанный если он содержит хотя бы k+1 вершин, но не содержит набора k − 1 вершины, удаление которых разъединяет граф; и κ(г) определяется как самый большой k такой, что г является k-связанный. В частности, полный график с участием п вершины, обозначенные Kп, совсем не имеет вершинных разрезов, но κ(Kп) = п − 1.
А вершинный разрез для двух вершин ты и v набор вершин, удаление которых из графа разъединяет ты и v. В локальная связь κ(ты, v) это размер наименьшей вершины сечения, разделяющей ты и v. Локальная связность симметрична для неориентированных графов; это, κ(ты, v) = κ(v, ты). Причем, кроме полных графов, κ(г) равно минимум κ(ты, v) по всем несмежным парам вершин u, v.
2-подключение также называется двусвязность и 3-подключение также называется трёхсвязность. График г который связан, но не 2-connected иногда называют отделяемый.
Аналогичные концепции можно определить для ребер. В простом случае, когда разрезание одного конкретного ребра разъединит граф, это ребро называется мост. В более общем смысле, обрезка кромки г - это набор ребер, удаление которых делает граф несвязным. В граничное соединение λ(г) - это размер наименьшего краевого среза, а локальное соединение ребер λ(ты, v) двух вершин u, v это размер наименьшего отсечения кромки ты от v. Опять же, локальная связность ребер симметрична. Граф называется k-ребневой если его граничное соединение k или выше.
Граф называется максимально связанный если его связность равна минимальной степени. Граф называется максимально реберный если его граничная связность равна его минимальной степени.[3]
Супер- и гипер-подключение
Граф называется сверхсвязанный или супер-κ если каждая минимальная вершина сечения изолирует вершину. Граф называется гипер-связанный или гипер-κ если удаление каждой минимальной вершины разреза создает ровно две компоненты, одна из которых является изолированной вершиной. График полугиперсвязный или полугипер-κ если любая минимальная вершина разрезания разделяет граф ровно на две составляющие.[4]
Точнее: а г связный граф называется сверхсвязанный или супер-κ если все минимальные вершинные разрезы состоят из вершин, смежных с одной вершиной (минимальной степени). г связный граф называется супер-связный или супер-λ если все минимальные реберные разрезы состоят из ребер, инцидентных некоторой вершине (минимальной степени).[5]
Cutset Икс из г называется нетривиальным сечением, если Икс не содержит окрестности N (u) любой вершины u ∉ X. Тогда сверхсвязанность κ1 группы G:
- κ1 (G) = min {| X | : X - нетривиальное сечение}.
Нетривиальная обрезка ребер и граничная сверхсвязь λ1 (G) определяются аналогично.[6]
Теорема Менгера
Один из наиболее важных фактов о связности графиков: Теорема Менгера, который характеризует связность и связность ребер графа с точки зрения количества независимых путей между вершинами.
Если ты и v вершины графа г, затем набор путей между ты и v называется независимым, если никакие два из них не имеют общей вершины (кроме ты и v самих себя). Точно так же коллекция не зависит от ребер, если никакие два пути в ней не имеют общего ребра. Количество взаимно независимых путей между ты и v записывается как κ ′(ты, v), и количество взаимно независимых от ребер путей между ты и v записывается как λ ′(ты, v).
Теорема Менгера утверждает, что для различных вершин ты,v, λ(ты, v) равно λ ′(ты, v), и если ты также не примыкает к v тогда κ(ты, v) равно κ ′(ты, v).[7][8] Фактически это частный случай теорема о максимальном потоке и минимальном отсечении.
Вычислительные аспекты
Проблема определения, связаны ли две вершины в графе, может быть эффективно решена с помощью алгоритм поиска, такие как поиск в ширину. В более общем плане легко определить с помощью вычислений, связан ли граф (например, с помощью непересекающаяся структура данных ) или подсчитать количество связанных компонентов. Простой алгоритм можно записать на псевдокод следующим образом:
- Начните с любого произвольного узла графа, г
- Начните с этого узла, используя поиск в глубину или в ширину, подсчитывая все достигнутые узлы.
- После того, как граф был полностью пройден, если количество подсчитанных узлов равно количеству узлов г, граф связный; в противном случае он отключается.
По теореме Менгера для любых двух вершин ты и v в связном графе г, число κ(ты, v) и λ(ты, v) можно эффективно определить с помощью макс. расход мин. обрезка алгоритм. Связь и граничная связь г затем можно вычислить как минимальные значения κ(ты, v) и λ(ты, v)соответственно.
В теории сложности вычислений SL это класс проблем сокращаемое пространство журнала к задаче определения, связаны ли две вершины в графе, которая оказалась равной L от Омер Рейнгольд в 2004 г.[9] Следовательно, связность неориентированного графа может быть решена в O (журнал п) Космос.
Проблема вычисления вероятности того, что Бернулли случайный граф связан, называется надежностью сети, а проблема вычисления, связаны ли две заданные вершины, проблемой ST-надежности. Оба они #П -жесткий.[10]
Количество связанных графов
Количество различных связных помеченных графов с п узлов сведены в таблицу Он-лайн энциклопедия целочисленных последовательностей как последовательность A001187, через п = 16. Первые несколько нетривиальных членов:
| п | графики |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Примеры
- Связности по вершинам и ребрам несвязного графа равны 0.
- 1-связность эквивалентна связности для графов не менее двух вершин.
- В полный график на п вершины имеют связность ребер, равную п − 1. Любой другой простой график на п вершины имеют строго меньшую связность ребер.
- В дерево, локальная связность ребер между каждой парой вершин равна 1.
Границы подключения
- Связность вершин графа меньше или равна его связности ребер. Это, κ(г) ≤ λ(г). Оба меньше или равны минимальная степень графа, поскольку удаление всех соседей вершины минимальной степени отключит эту вершину от остальной части графа.[1]
- Для вершинно-транзитивный граф из степень d, у нас есть: 2(d + 1)/3 ≤ κ(г) ≤ λ(г) = d.[11]
- Для вершинно-транзитивный граф из степень d ≤ 4, или для любого (неориентированного) минимального Граф Кэли из степень d, или для любого симметричный граф из степень d, оба вида подключения равны: κ(г) = λ(г) = d.[12]
Другие свойства
- Связность сохраняется гомоморфизмы графов.
- Если г связано то его линейный график L(г) тоже связано.
- График г является 2-ребневой если и только если у него есть сильно связная ориентация.
- Теорема Балинского заявляет, что многогранный граф (1-скелет ) из k-мерная выпуклая многогранник это k-вершинно-связный граф.[13] Steinitz Предыдущая теорема о том, что любая 3-вершинно-связная планарный граф является многогранным графом (Теорема Штейница ) дает частичное обратное.
- Согласно теореме Г. А. Дирак, если граф k-подключен для k ≥ 2, то для каждого набора k вершин в графе существует цикл, который проходит через все вершины в множестве.[14][15] Обратное верно, когда k = 2.
Смотрите также
- Алгебраическая связность
- Константа Чигера (теория графов)
- Динамическое подключение, Непересекающаяся структура данных
- График расширителя
- Сила графика
использованная литература
- ^ а б Дистель, Р. (2005). "Теория графов, электронное издание". п. 12.
- ^ Глава 11: Орграфы: принцип двойственности орграфов: определение
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2004). Справочник по теории графов. CRC Press. п.335. ISBN 978-1-58488-090-5.
- ^ Лю, Цинхай; Чжан, Чжао (01.03.2010). «Существование и верхняя граница для двух типов ограниченного подключения». Дискретная прикладная математика. 158 (5): 516–521. Дои:10.1016 / j.dam.2009.10.017.
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2004). Справочник по теории графов. CRC Press. п.338. ISBN 978-1-58488-090-5.
- ^ Балбуэна, Камино; Кармона, Анхелес (2001-10-01). «О связности и сверхсвязности двудольных орграфов и графов». Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
- ^ Гиббонс, А. (1985). Алгоритмическая теория графов. Издательство Кембриджского университета.
- ^ Nagamochi, H .; Ибараки, Т. (2008). Алгоритмические аспекты связности графов. Издательство Кембриджского университета.
- ^ Рейнгольд, Омер (2008). «Ненаправленное соединение в лог-пространстве». Журнал ACM. 55 (4): 1–24. Дои:10.1145/1391289.1391291. S2CID 207168478.
- ^ Прован, Дж. Скотт; Болл, Майкл О. (1983). «Сложность подсчета сокращений и вычисления вероятности того, что граф связан». SIAM Журнал по вычислениям. 12 (4): 777–788. Дои:10.1137/0212053. Г-Н 0721012..
- ^ Годсил, К.; Ройл, Г. (2001). Алгебраическая теория графов. Springer Verlag.
- ^ Бабай, Л. (1996). Группы автоморфизмов, изоморфизм, реконструкция. Технический отчет TR-94-10. Чикагский университет. Архивировано из оригинал на 2010-06-11. Глава 27 Справочник по комбинаторике.
- ^ Балински, М. Л. (1961). «О графическом строении выпуклых многогранников в п-Космос". Тихоокеанский математический журнал. 11 (2): 431–434. Дои:10.2140 / pjm.1961.11.431.[постоянная мертвая ссылка ]
- ^ Дирак, Габриэль Эндрю (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. Дои:10.1002 / мана.19600220107. Г-Н 0121311..
- ^ Фландрин, Эвелин; Ли, Хао; Марчик, Антони; Возняк, Мариуш (2007). "Обобщение теоремы Дирака о циклах через k вершины в k-связные графы ». Дискретная математика. 307 (7–8): 878–884. Дои:10.1016 / j.disc.2005.11.052. Г-Н 2297171..