Изменения

'''Вершинной связностью''' <tex>\varkappakappa</tex> графа <tex>G</tex> (англ. ''vertex-connectivity'') называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

'''Реберной связностью''' <tex>\lambda</tex> графа <tex>G</tex> (англ. ''edge-connectivity'') называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.

Для любого графа <tex>G</tex> справедливо следующее неравенство: <tex>\varkappa kappa \leleqslant \lambda \le leqslant \delta </tex>

[[Файл:Ver_ed_coh_1.png|thumb|right|150px|Полный граф. <tex> \lambda = \delta = \varkappa kappa = 4</tex>]]# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \le leqslant \delta </tex>.

##Если <tex>G</tex> {{--- }} несвязный или тривиальный граф, то <tex> \varkappa kappa = \lambda = 0 </tex>. ##Если <tex>G</tex> связен и имеет мост <tex>x</tex>, то <tex>\lambda = 1 </tex>. В последнем случае <tex> \varkappa kappa = 1 </tex>, поскольку или граф <tex>G</tex> имеет точку сочленения, инцидентную ребру <tex>x</tex>, или же <tex>G=K_2</tex>. ##Наконец, предположим, что граф <tex>G</tex> содержит множество из <tex> \lambda \ge 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>\varkappa < kappa \lt \lambda</tex>; если же он связен, то в нем есть мост <tex>x</tex>, и поэтому удаление вершины <tex>u</tex> или <tex>v</tex> приводит либо к несвязному, либо к тривиальному графу. В любом случае <tex> \varkappa kappa \le leqslant \lambda</tex>.

Для любых натуральных чисел <tex>a, b, c</tex>, таких что <tex>a \le leqslant b \le leqslant c</tex>, существует граф <tex>G</tex>, у которого <tex>\varkappa kappa = a, \lambda = b</tex> и <tex>\delta = c </tex>|proof=[[Файл:Ver_ed_coh_2.png|thumb|right|335px|Граф, в котором <tex> \delta = 4</tex>, <tex>\lambda = 3</tex>, <tex>\varkappa kappa = 2</tex>.]]

# Поскольку <tex>b \le leqslant c</tex>, то было как минимум две непомеченные вершины, поэтому <tex> \delta = c</tex>, так как минимальные степени вершин графов <tex>G_1</tex> и <tex>G_2</tex> были равны <tex>c</tex>, а степени их вершин не уменьшались.# Заметим, что между двумя вершинами графа <tex>G</tex> существует не меньше <tex>a</tex> вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <tex>\varkappa kappa \ge geqslant a</tex>. Однако если удалить из графа <tex>G</tex> помеченные вершины его подграфа <tex>G_2</tex>, то граф <tex>G</tex> потеряет связность. Значит, <tex>\varkappa kappa = a</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> и найдем максимальный [[Определение сети, потока #Определение потока |поток]] (например, [[Алгоритм Эдмондса-Карпа|алгоритм Эдмондса-Карпа]]).

'''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>

Нахождение Используя аналогичные утверждения и определения для вершинной связности сводится придем к задаче нахождения реберной связности следующим образомтакому же алгоритму с тем отличием, что понадобится искать вершинно-непересекающиеся пути.Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную <tex>1</tex>.Для этого воспользуемся известным трюком:

Разобьем каждую вершину <tex>v</tex> графа на две вершины <tex>v_1</tex> и <tex>v_2</tex>. Все ребра, которые входили в <tex>v</tex> будут входить в <tex>v_1</tex>. Все ребра, которые выходили из <tex>v</tex> будут выходить из <tex>v_2</tex>. Так же добавим ребро <tex>(v_1, v_2)</tex> с пропускной способностью <tex>1</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>нахождению реберной связности.

''' Псевдокод алгоритма ''' ans = INF for <tex>s \in V:</tex> for <tex>t \in V:</tex> flow = find_flow(s, t) ans См. также== min(ans, flow)

== Нахождение вершинной связности ==Нахождение вершинной связности сводится к задаче нахождения реберной связности следующим образом* [https://stugum.files.wordpress.com/2014/03/harary-graph-theory.pdf Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.]

Разобьем каждую вершину <tex>v<* [http:/tex> графа на две вершины <tex>v_1</tex> и <tex>v_2<alleng.org/tex>. Все ребра, которые входили в <tex>v<d/tex> будут входить в <tex>v_1<comp/tex>comp384. Все ребраhtm Дж. Клейнберг, которые выходили из <tex>v</tex> будут выходить из <tex>v_2</tex>Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016. Так же добавим ребро <tex>(v_1, v_2)</tex>- 383 c.]