Связность в графах кратко

Обновлено: 05.07.2024

Рассмотрим вопрос о связности в графах. Пусть G(X) – неориентированный граф. Две вершины х_i и x_j называются связными, если существует цепь S с концами х_i и x_j. Если S проходит через некоторую вершину x_k более одного раза, то можно удалить цикл в вершине x_k из цепи S. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.

Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности
(x_i ~ x_j, х_j ~ х_k Û x_i ~ х_k).

Компонентой связности неориентированного графа G(X) называется подграф Н_А(А) графа G(X) с множеством вершин А Ì X и множеством ребер в G(X), инцидентных только вершинам из А, причем ни одна вершина x_i Î А не смежна с вершинами из множества Х \ А (рис. 3.12).

Рис. 3.12. Граф с двумя компонентами связности

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

Компонентой сильной связности ориентированного графа G(X) называется подграф Н_А(А) графа G(Х) (подчиняющийся определению сильно связного графа) с множеством вершин А Ì Х и множеством дуг, имеющих начало и конец в А, причем ни одна из вершин х_i Î А и х_j Î X \ А не смежны между собой (рис. 3.13).

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

Очевидно, что ориентированный граф G(X) сильно связан тогда и только тогда, когда он имеет одну компоненту связности.

На практике широко используются такие виды графов, как деревья и прадеревья.

Деревом называется конечный связный неориентированный граф, состоящий, по крайней мере, из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер (рис. 3.14).

Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву. Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.

Лесомназывается несвязный граф, каждая компонента связности которого является деревом.

Прадеревом называется ориентированный граф G(X) с корнем х₀ Î X, если в каждую вершину х_i ¹ х₀ (х_i Î X) заходит ровно одна дуга, а в корень х₀ не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).

Рис. 3.15. Прадерево

Рис. 3.12. Граф с двумя компонентами связности

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

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

На практике широко используются такие виды графов, как деревья и прадеревья.

Лесомназывается несвязный граф, каждая компонента связности которого является деревом.

В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.

Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.

Например, граф на рисунке состоит из 8 вершин и 8 рёбер.

Очень многие задачи могут быть решены используя богатую библиотеку алгоритмов теории графов. Для этого достаточно лишь принять объекты за вершины, а связь между ними - за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам: нахождение маршрута от одного объекта к другому, поиск связанных компонент, вычисление кратчайших путей, поиск сети максимального потока и многое другое.

В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.

Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.

Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.

Инцидентность - вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.

Смежность вершин - две вершины называются смежными, если они инцидентны одному ребру.

Смежность рёбер - два ребра называются смежными, если они инцедентны одной вершине.

Говоря проще - две вершины смежные, если они соединены ребром, два ребра смежные - если они соединены вершиной.

Петля - ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.

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

Кратные рёбра - рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.

Мультиграф - граф с кратными рёбрами.

Псевдомультиграф - граф с петлями и кратными рёбрами.

Степень вершины - это количество рёбер, инцидентных указанной вершине. По-другому - количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.

Изолированная вершина - вершина с нулевой степенью.

Висячая вершина - вершина со степенью 1.

Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа.

Идея подграфов используется во многих алгоритмах, например, сначала создаётся подграф их всех вершин без рёбер, а потом дополняется выбранными рёбрами.

Полный граф - это граф, в котором каждые две вершины соединены одним ребром.

Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N - каждый новый участник должен пожать руку всем присутствующим. Сумму нужно разделить на два, так как в этом случае каждое рукопожатие посчитается дважды: N * (N - 1) / 2.

Регулярный граф - граф, в котором степени всех вершин одинаковые.

Двудольный граф - если все вершины графа можно разделить на два множества таким образом, что каждое ребро соединяет вершины из разных множеств, то такой граф называется двудольным. Например, клиент-серверное приложение содержит множество запросов (рёбер) между клиентом и сервером, но нет запросов внутри клиента или внутри сервера.

Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.

Если это невозможно сделать, то граф называется “непланарным”.

Минимальные непланарные графы - это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.

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

Длина пути - количество рёбер в пути.

Цепь - маршрут без повторяющихся рёбер.

Простая цепь - цепь без повторяющихся вершин.

Цикл или Контур - цепь, в котором последняя вершина совпадает с первой.

Длина цикла - количество рёбер в цикле.

Самый короткий цикл - это петля.

Цикл Эйлера - цикл, проходящий по каждому ребру ровно один раз. Эйлер доказал, что такой цикл существует тогда, и только тогда, когда все вершины в связанном графе имеют чётную степень.

Цикл Гамильтона - цикл, проходящий через все вершины графа по одному разу. Другими словами - это простой цикл, в который входят все вершины графа.

Взвешенный граф - граф, в котором у каждого ребра и/или каждой вершины есть “вес” - некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.

Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса - “Алгоритмы и структуры данных”.

Связный граф - граф, в котором существует путь между любыми двумия вершинами.

Дерево - связный граф без циклов.

Между любыми двумя вершинами дерева существует единственный путь.

Деревья часто используются для организации иерархической структуры данных, например, при создании двоичных деревьев поиска или кучи, в этом случае одну вершину дерева называют корнем.

Лес - граф, в котором несколько деревьев.

Ориентированный граф или Орграф - граф, котором рёбра имеют направления.

Дуга - направленные рёбра в ориентированном графе.

Полустепень захода вершины - количество дуг, заходящих в эту вершину.

Исток - вершина с нулевой полустепенью захода.

Полустепень исхода вершины - количество дуг, исходящих из этой вершины

Сток - вершина с нулевой полустепенью исхода.

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

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

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

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

Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи - дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.

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

Содержание

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

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

Ориентированный граф называется слабо связным , если замена все его ориентированных ребер с неориентированными ребрами производит связной (неориентированный граф). Он является односторонне связным или односторонним (также называемым полусвязным ), если он содержит направленный путь от 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 ) определяется как по величине к таким образом, что G является к -связной. В частности, полный граф с n вершинами, обозначенный K _n , вообще не имеет вершинных разрезов, но κ ( K _n ) = n - 1 .

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

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

Аналогичные концепции можно определить для ребер. В простом случае, когда разрезание одного конкретного ребра разъединит граф, это ребро называется мостом . В более общем смысле, реберный разрез G - это набор ребер, удаление которых делает граф несвязным. Ребра связности λ ( G ) является размер наименьшего края разреза, а местная края подключения λ ( U , V ) из двух вершин U, V является размер наименьшего края среза отсоединением U от V . Опять же, локальная связность ребер симметрична. Граф называется k- реберно-связным. если его граничное соединение равно k или больше.

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

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

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

Cutset Х из G называется нетривиальной cutset , если Й не содержат окрестности N (U) любой вершину у ∉ х . Тогда superconnectivity κ1 из G является:

Нетривиальные края разрез и кромка-superconnectivity λ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 является класс задач лог-пространства приводимым к задаче определения , связаны ли две вершины в графе, что было доказано , чтобы быть равным L от Omer Рейнгольдом в 2004 году [9] Таким образом, неориентированного графа возможность подключения может быть решена в пространстве O (log n ) .

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

Пусть задан (ориентированный или неориентированный) граф [math]G = (V, E)[/math] . Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math] , [math]e_2 = (w_1, w_2)[/math] , …, [math]e_k = (w_, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math] . В этом случае вершина [math]v[/math] достижима из вершины [math]u[/math] . Считается, что от вершины [math]u[/math] к себе самой ведёт пустой путь [math]P(u, u)[/math] , то есть каждая вершина достижима из самой себя. Непустой путь [math]P(u, u)[/math] называется циклом (замкнутым обходом).

Неориентированный граф называется связным, если все его вершины достижимы из некоторой вершины (эквивалентно, из любой его вершины).

Ориентированный граф называется

слабо связным, если соответствующий неориентированный граф является связным;
сильно связным, если всякая вершина [math]v[/math] достижима из любой другой вершины [math]v[/math] .

Компонентой связности неориентированного графа называется максимальный по включению связный подграф.

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

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

Шарниром в графе называется вершина, удаление которой увеличивает число компонент связности.

Связный граф называется вершинно- [math]k[/math] -связным (или просто [math]k[/math] -связным), если он имеет более [math]k[/math] вершин и после удаления любых [math]k-1[/math] из них остаётся связным. Максимальное такое число [math]k[/math] называется вершинной связностью (или просто связностью) графа. 1-связный граф называется связным, 2-связный граф – двусвязным.

Связный граф называется рёберно- [math]k[/math] -связным, если он остаётся связным после удаления любых [math]k-1[/math] рёбер. Максимальное такое число [math]k[/math] называется рёберной связностью графа.

Компонентой двусвязности графа называется максимальный по включению двусвязный подграф.

2 Свойства

Эквивалентные определения компоненты связности:

все вершины, достижимые из какой-либо выбранной вершины;
набор вершин, достижимых друг из друга, и не достижимых из других вершин.

Альтернативные определения моста:

ребро является мостом, если не участвует ни в одном цикле;
ребро [math]e[/math] является мостом, если существует пара вершин [math](u, v)[/math] из одной компоненты связности, любой путь [math]P(u, v)[/math] между которыми проходит через ребро [math]e[/math] .

Шарнир разделяет компоненты двусвязности (если две компоненты двусвязности имеют общую вершину, то это шарнир).

Каждая из вершин моста является шарниром (кроме случая, когда мост является единственным ребром этой вершины).

Компонента сильной связности является объединением всех циклом, проходящих через её вершины.

3 Алгоритмы

Компоненты связности могут быть найдены:

последовательным применением алгоритма поиска в ширину за время [math]O(m)[/math] ;
с помощью системы непересекающихся множеств[1] за время [math]O(m \alpha(m, n))[/math] , с возможностью эффективной многопоточной реализации [2] ;
параллельным алгоритмом Шилоаха-Вишкина[3] за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.

Компоненты сильной связности могут быть найдены:

[4] (в ходе поиска в глубину) за время [math]O(m)[/math] ; [5][6][7] с работой [math]O(n \ln n)[/math] .

Мосты могут быть найдены:

параллельным алгоритмом Тарьяна-Вишкина[9] за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах;
онлайн-алгоритмом Уэстбрука-Тарьяна [10] за время [math]O(m \alpha(m, n))[/math] .

Компоненты двусвязности могут быть найдены:

параллельным алгоритмом Тарьяна-Вишкина[11] за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах (алгоритм также может находить и мосты);
онлайн-алгоритмом Уэстбрука-Тарьяна [10] за время [math]O(m \alpha(m, n))[/math] .

Рёберная связность графа может быть найдена алгоритмом Габова [13] за время [math]O(k m \ln (n^2/m))[/math] для ориентированного и [math]O(m + k^2 n \ln (n/k))[/math] неориентированного графа. Проверка свойства [math]k[/math] -связности тем же алгоритмом может быть выполнена за время [math]O(m + n \ln n)[/math] .

Читайте также: