105
правок
Изменения
м
В статье про [[k-связность]] было сформулировано следующее утверждение:
{{Утверждение
|statement=
Граф <tex> G </tex> является '''реберно <tex> l </tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
}}
Там же было дано определение реберной связности через <tex> l </tex>-связность:
{{Определение
|definition=
[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex>- связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.
}}
Дмитрий Мурзин переименовал страницу Вершинная, реберная связность, связь между ними и минимальной степенью вершины в [[Вершинная, рёб…
{{Определение
|definition=
'''Вершинной связностью''' <tex>\kappa</tex> графа <tex>G</tex> (англ. ''vertex-connectivity'') называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Определение
|definition=
'''Реберной связностью''' <tex>\lambda</tex> графа <tex>G</tex> (англ. ''edge-connectivity'') называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
}}
# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \leqslant \delta </tex>.
# Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.
##Если <tex>G</tex> {{- --}} несвязный или тривиальный граф, то <tex> \kappa = \lambda = 0 </tex>.
##Если <tex>G</tex> связен и имеет мост <tex>x</tex>, то <tex>\lambda = 1 </tex>. В последнем случае <tex> \kappa = 1 </tex>, поскольку или граф <tex>G</tex> имеет точку сочленения, инцидентную ребру <tex>x</tex>, или же <tex>G=K_2</tex>.
##Наконец, предположим, что граф <tex>G</tex> содержит множество из <tex> \lambda \geqslant 2 </tex> ребер, удаление которых делает его несвязным. Ясно, что удаляя <tex>\lambda - 1 </tex> ребер из этого множества получаем граф, имеющий мост <tex>x = uv</tex>. Для каждого из этих <tex>\lambda - 1 </tex> ребер выберем какую-либо инцидентную с ним вершину отличную от <tex>u</tex> и <tex>v</tex>. Удаление выбранных вершин приводит к удалению <tex>\lambda - 1 </tex> (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то <tex>\kappa \lt \lambda</tex>; если же он связен, то в нем есть мост <tex>x</tex>, и поэтому удаление вершины <tex>u</tex> или <tex>v</tex> приводит либо к несвязному, либо к тривиальному графу. В любом случае <tex> \kappa \leqslant \lambda</tex>.
== Нахождение реберной связности ==
Для нахождения реберной связности нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум.
Пусть он равен <tex>l</tex>. По утверждению, граф является [[k-связность#def_2|<tex>l</tex>-связным]], причем такое <tex>l</tex> {{--- }} максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна <tex>l</tex>.
Для нахождения количества непересекающихся путей из <tex>s</tex> в <tex>t</tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1</tex> и найдем максимальный [[Определение сети, потока #Определение потока |поток]](например, [[Алгоритм Эдмондса-Карпа|алгоритм Эдмондса-Карпа]]).
Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из <tex>s</tex> в <tex>t</tex>, по которым поток неотрицателен и равен <tex>1</tex> (т.к. пропускная способность всех ребер равна <tex>1</tex>). А значит, если поток равен <tex>flow</tex>, то и количество путей равно <tex>flow</tex>.
''' Псевдокод алгоритма '''
'''function''' disjoint_paths_count(): '''int''' ans = INF '''for''' <tex>s \in V:</tex> '''for''' <tex>t \in V:</tex> flow = find_flowfind_max_flow(s, t) <font color=darkgreen>// максимальный поток {{- --}} количество путей из <tex>s </tex> в <tex>t</tex> </font> ans = min(ans, flow) '''return''' ans
'''Оценка работы'''
Время работы равно <tex>V^2 \times O(find\_max\_flow)</tex>. При использовании [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] время равно <tex>V^2 \times O(V E^2)</tex> или <tex>O(V^3 E^2)</tex>
== Нахождение вершинной связности ==
*[[Теорема Менгера]]
*[[Алгоритм Эдмондса-Карпа]]
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%BE%D0%B1%D0%B1%D0%B8%D0%BD%D1%81%D0%B0 Википедия {{---}} Теорема Роббинса]
==Источники информации==
* [https://stugum.files.wordpress.com/2014/03/harary-graph-theory.pdf Харари Ф. '''Теория графов''': Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с. ] * [http://alleng.org/d/comp/comp384.htm Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016. - 383 c.]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
