Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Нахождение реберной связности)
м (Дмитрий Мурзин переименовал страницу Вершинная, реберная связность, связь между ними и минимальной степенью вершины в [[Вершинная, рёб…)
(не показаны 34 промежуточные версии 4 участников)
Строка 1: Строка 1:
== Определения ==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Вершинной связностью''' <tex>\varkappa</tex> графа <tex>G</tex> называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
+
'''Вершинной связностью''' <tex>\kappa</tex> графа <tex>G</tex> (англ. ''vertex-connectivity'') называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Реберной связностью''' <tex>\lambda</tex> графа <tex>G</tex> называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
+
'''Реберной связностью''' <tex>\lambda</tex> графа <tex>G</tex> (англ. ''edge-connectivity'') называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  
Строка 14: Строка 13:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для любого графа <tex>G</tex> справедливо следующее неравенство: <tex>\varkappa \le\lambda \le \delta </tex>
+
Для любого графа <tex>G</tex> справедливо следующее неравенство: <tex>\kappa \leqslant \lambda \leqslant \delta </tex>
 
|proof=
 
|proof=
[[Файл:Ver_ed_coh_1.png|thumb|right|150px|Полный граф. <tex> \lambda = \delta = \varkappa = 4</tex>]]
+
[[Файл:Ver_ed_coh_1.png|thumb|right|150px|Полный граф. <tex> \lambda = \delta = \kappa = 4</tex>]]
# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \le \delta </tex>.  
+
# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \leqslant \delta </tex>.  
 
# Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.  
 
# Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.  
##Если  <tex>G</tex> - несвязный или тривиальный граф, то  <tex> \varkappa = \lambda = 0 </tex>.  
+
##Если  <tex>G</tex> {{---}} несвязный или тривиальный граф, то  <tex> \kappa = \lambda = 0 </tex>.  
##Если <tex>G</tex> связен и имеет мост <tex>x</tex>, то <tex>\lambda = 1 </tex>. В последнем случае <tex> \varkappa = 1 </tex>, поскольку или граф <tex>G</tex> имеет точку сочленения, инцидентную ребру <tex>x</tex>, или же <tex>G=K_2</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 \ge 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 < \lambda</tex>; если же он связен, то в нем есть мост <tex>x</tex>, и поэтому удаление вершины <tex>u</tex> или <tex>v</tex> приводит либо к несвязному, либо к тривиальному графу. В любом случае <tex> \varkappa \le \lambda</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>.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Для любых натуральных чисел <tex>a, b, c</tex>, таких что <tex>a \le b \le c</tex>, существует граф <tex>G</tex>, у которого <tex>\varkappa = a, \lambda  = b</tex> и <tex>\delta = c </tex>
+
  Для любых натуральных чисел <tex>a, b, c</tex>, таких что <tex>a \leqslant b \leqslant c</tex>, существует граф <tex>G</tex>, у которого <tex>\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 = 2</tex>.]]
+
|proof=[[Файл:Ver_ed_coh_2.png|thumb|right|335px|Граф, в котором <tex> \delta = 4</tex>, <tex>\lambda = 3</tex>, <tex>\kappa = 2</tex>.]]
 
Рассмотрим граф <tex>G</tex>, являющийся объединением двух полных графов <tex>G_1</tex> и <tex>G_2</tex>, содержащих <tex>c + 1</tex> вершину. Отметим <tex>b</tex> вершин, принадлежащих подграфу <tex>G_1</tex> и <tex>a</tex> вершин, принадлежащих подграфу <tex>G_2</tex>. Добавим в граф <tex>G</tex> <tex>b</tex> ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в  подграфе <tex>G_1</tex> и помеченной вершине, лежащей в подграфе <tex>G_2</tex>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
 
Рассмотрим граф <tex>G</tex>, являющийся объединением двух полных графов <tex>G_1</tex> и <tex>G_2</tex>, содержащих <tex>c + 1</tex> вершину. Отметим <tex>b</tex> вершин, принадлежащих подграфу <tex>G_1</tex> и <tex>a</tex> вершин, принадлежащих подграфу <tex>G_2</tex>. Добавим в граф <tex>G</tex> <tex>b</tex> ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в  подграфе <tex>G_1</tex> и помеченной вершине, лежащей в подграфе <tex>G_2</tex>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
 
Тогда:
 
Тогда:
  
# Поскольку <tex>b \le c</tex>, то было как минимум две непомеченные вершины, поэтому <tex> \delta = c</tex>, так как минимальные степени вершин графов <tex>G_1</tex> и <tex>G_2</tex> были равны <tex>c</tex>, а степени их вершин не уменьшались.
+
# Поскольку <tex>b \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 \ge a</tex>. Однако если удалить из графа <tex>G</tex> помеченные вершины его подграфа <tex>G_2</tex>, то граф <tex>G</tex> потеряет связность. Значит, <tex>\varkappa = a</tex>.
+
# Заметим, что между двумя вершинами графа <tex>G</tex> существует не меньше <tex>a</tex> вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <tex>\kappa \geqslant a</tex>. Однако если удалить из графа <tex>G</tex> помеченные вершины его подграфа <tex>G_2</tex>, то граф <tex>G</tex> потеряет связность. Значит, <tex>\kappa = a</tex>.
 
# Аналогично рассуждению пункта 2, легко убедится, что <tex>\lambda = b</tex>.
 
# Аналогично рассуждению пункта 2, легко убедится, что <tex>\lambda = b</tex>.
 
}}
 
}}
  
 
== Нахождение реберной связности ==
 
== Нахождение реберной связности ==
Для нахождения реберной связности воспользуемся [[Теорема Менгера, альтернативное доказательство|следующей теоремой:]]
 
{{Теорема
 
|about=
 
Теорема Менгера для <tex>k</tex>-реберной связности
 
|statement=
 
Пусть <tex>G</tex> - конечный, неориентированный граф, <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex>  для всех пар вершин <tex>x, y \in G</tex> существует <tex>k</tex> реберно непересекающихся путей из <tex>x</tex> в <tex>y</tex>.
 
}}
 
Алгоритм следует непосредственно из теоремы. Нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум.
 
  
Для нахождения количества непересекающихся путей из <tex>s</tex> в <tex>t</tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1</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>.
 
Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из <tex>s</tex> в <tex>t</tex>, по которым поток неотрицателен и равен <tex>1</tex> (т.к. пропускная способность всех ребер равна <tex>1</tex>). А значит, если поток равен <tex>flow</tex>, то и количество путей равно <tex>flow</tex>.
  
 
''' Псевдокод алгоритма '''
 
''' Псевдокод алгоритма '''
   ans = INF
+
   '''function''' disjoint_paths_count(): '''int'''
  for <tex>s \in V:</tex>
+
    ans = INF
    for <tex>t \in V:</tex>
+
    '''for''' <tex>s \in V:</tex>
      flow = find_flow(s, t)
+
        '''for''' <tex>t \in V:</tex>
      ans = min(ans, flow)
+
              flow = find_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\_flow)</tex>. При использовании [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] время равно <tex>V^2 \times O(V E^2)</tex> или <tex>O(V^3 E^2)</tex>
+
Время работы равно <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>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>.
  
 
[[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]]
 
[[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]]
 
<br clear="all"/>
 
<br clear="all"/>
В новом графе запустим алгоритм нахождения реберной связности.
 
== Нахождение реберной связности. ver 2.0 ==
 
Для нахождения реберной связности воспользуемся [[Теорема Менгера, альтернативное доказательство|следующей теоремой:]]
 
{{Теорема
 
|about=
 
Теорема Менгера для <tex>k</tex>-реберной связности
 
|statement=
 
Пусть <tex>G</tex> - конечный, неориентированный граф, <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex>  для всех пар вершин <tex>x, y \in G</tex> существует <tex>k</tex> реберно непересекающихся путей из <tex>x</tex> в <tex>y</tex>.
 
}}
 
Алгоритм следует непосредственно из теоремы. Нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</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://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 Википедия {{---}} Теорема Роббинса]
  
Время работы равно <tex>V^2 \times O(find\_flow)</tex>. При использовании [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] время равно <tex>V^2 \times O(V E^2)</tex> или <tex>O(V^3 E^2)</tex>
+
==Источники информации==
  
== Нахождение вершинной связности. ver 2.0 ==
+
* [https://stugum.files.wordpress.com/2014/03/harary-graph-theory.pdf Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.]
Нахождение вершинной связности сводится к задаче нахождения реберной связности следующим образом.
 
  
Разобьем каждую вершину <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>.
+
* [http://alleng.org/d/comp/comp384.htm Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016. - 383 c.]
  
[[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]]
 
<br clear="all"/>
 
В новом графе запустим алгоритм нахождения реберной связности.
 
  
== Литература ==
 
* Харари Ф. '''Теория графов''': Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Связность в графах]]
 
[[Категория: Связность в графах]]

Версия 23:34, 31 января 2019

Определение:
Вершинной связностью [math]\kappa[/math] графа [math]G[/math] (англ. vertex-connectivity) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.


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


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

Пускай минимальная степень вершины графа [math]G[/math] обозначается буквой [math]\delta[/math]. Тогда:

Теорема:
Для любого графа [math]G[/math] справедливо следующее неравенство: [math]\kappa \leqslant \lambda \leqslant \delta [/math]
Доказательство:
[math]\triangleright[/math]
Полный граф. [math] \lambda = \delta = \kappa = 4[/math]
  1. Проверим второе неравенство. Если в графе [math]G[/math] нет ребер, то [math] \lambda = 0 [/math]. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае [math] \lambda \leqslant \delta [/math].
  2. Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.
    1. Если [math]G[/math] — несвязный или тривиальный граф, то [math] \kappa = \lambda = 0 [/math].
    2. Если [math]G[/math] связен и имеет мост [math]x[/math], то [math]\lambda = 1 [/math]. В последнем случае [math] \kappa = 1 [/math], поскольку или граф [math]G[/math] имеет точку сочленения, инцидентную ребру [math]x[/math], или же [math]G=K_2[/math].
    3. Наконец, предположим, что граф [math]G[/math] содержит множество из [math] \lambda \geqslant 2 [/math] ребер, удаление которых делает его несвязным. Ясно, что удаляя [math]\lambda - 1 [/math] ребер из этого множества получаем граф, имеющий мост [math]x = uv[/math]. Для каждого из этих [math]\lambda - 1 [/math] ребер выберем какую-либо инцидентную с ним вершину отличную от [math]u[/math] и [math]v[/math]. Удаление выбранных вершин приводит к удалению [math]\lambda - 1 [/math] (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то [math]\kappa \lt \lambda[/math]; если же он связен, то в нем есть мост [math]x[/math], и поэтому удаление вершины [math]u[/math] или [math]v[/math] приводит либо к несвязному, либо к тривиальному графу. В любом случае [math] \kappa \leqslant \lambda[/math].
[math]\triangleleft[/math]
Теорема:
Для любых натуральных чисел [math]a, b, c[/math], таких что [math]a \leqslant b \leqslant c[/math], существует граф [math]G[/math], у которого [math]\kappa = a, \lambda = b[/math] и [math]\delta = c [/math]
Доказательство:
[math]\triangleright[/math]
Граф, в котором [math] \delta = 4[/math], [math]\lambda = 3[/math], [math]\kappa = 2[/math].

Рассмотрим граф [math]G[/math], являющийся объединением двух полных графов [math]G_1[/math] и [math]G_2[/math], содержащих [math]c + 1[/math] вершину. Отметим [math]b[/math] вершин, принадлежащих подграфу [math]G_1[/math] и [math]a[/math] вершин, принадлежащих подграфу [math]G_2[/math]. Добавим в граф [math]G[/math] [math]b[/math] ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе [math]G_1[/math] и помеченной вершине, лежащей в подграфе [math]G_2[/math], причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:

  1. Поскольку [math]b \leqslant c[/math], то было как минимум две непомеченные вершины, поэтому [math] \delta = c[/math], так как минимальные степени вершин графов [math]G_1[/math] и [math]G_2[/math] были равны [math]c[/math], а степени их вершин не уменьшались.
  2. Заметим, что между двумя вершинами графа [math]G[/math] существует не меньше [math]a[/math] вершинно-непересекающихся простых цепей, следовательно по теореме Менгера [math]\kappa \geqslant a[/math]. Однако если удалить из графа [math]G[/math] помеченные вершины его подграфа [math]G_2[/math], то граф [math]G[/math] потеряет связность. Значит, [math]\kappa = a[/math].
  3. Аналогично рассуждению пункта 2, легко убедится, что [math]\lambda = b[/math].
[math]\triangleleft[/math]

Нахождение реберной связности

Для нахождения реберной связности нужно перебрать все пары вершин [math]s[/math] и [math]t[/math], найти количество непересекающихся путей из [math]s[/math] в [math]t[/math] и выбрать минимум. Пусть он равен [math]l[/math]. По утверждению, граф является [math]l[/math]-связным, причем такое [math]l[/math] — максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна [math]l[/math].

Для нахождения количества непересекающихся путей из [math]s[/math] в [math]t[/math] воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную [math]1[/math] и найдем максимальный поток (например, алгоритм Эдмондса-Карпа). Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из [math]s[/math] в [math]t[/math], по которым поток неотрицателен и равен [math]1[/math] (т.к. пропускная способность всех ребер равна [math]1[/math]). А значит, если поток равен [math]flow[/math], то и количество путей равно [math]flow[/math].

Псевдокод алгоритма

 function disjoint_paths_count(): int
   ans = INF
   for [math]s \in V:[/math]
        for [math]t \in V:[/math]
             flow = find_max_flow(s, t) // максимальный поток — количество путей из [math]s[/math] в [math]t[/math] 
             ans = min(ans, flow)
   return ans

Оценка работы

Время работы равно [math]V^2 \times O(find\_max\_flow)[/math]. При использовании алгоритма Эдмондса-Карпа время равно [math]V^2 \times O(V E^2)[/math] или [math]O(V^3 E^2)[/math]

Нахождение вершинной связности

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

Разобьем каждую вершину [math]v[/math] графа на две вершины [math]v_1[/math] и [math]v_2[/math]. Все ребра, которые входили в [math]v[/math] будут входить в [math]v_1[/math]. Все ребра, которые выходили из [math]v[/math] будут выходить из [math]v_2[/math]. Так же добавим ребро [math](v_1, v_2)[/math] с пропускной способностью [math]1[/math].

Иллюстрация


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

Тем самым сведя задачу к нахождению реберной связности.

См. также

Источники информации