Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями
Vsklamm (обсуждение | вклад) м (→См. также) |
м (Дмитрий Мурзин переименовал страницу Вершинная, реберная связность, связь между ними и минимальной степенью вершины в [[Вершинная, рёб…) |
||
(не показано 13 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Вершинной связностью''' <tex>\kappa</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'') называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу. |
}} | }} | ||
Строка 18: | Строка 18: | ||
# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \leqslant \delta </tex>. | # Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \leqslant \delta </tex>. | ||
# Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. | # Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. | ||
− | ##Если <tex>G</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>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>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>. | ||
Строка 35: | Строка 35: | ||
== Нахождение реберной связности == | == Нахождение реберной связности == | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Для нахождения реберной связности нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум. | Для нахождения реберной связности нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум. | ||
− | Пусть он равен <tex>l</tex>. По утверждению, граф является <tex>l</tex>-связным, причем такое <tex>l</tex> - максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна <tex>l</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>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>. | ||
Строка 57: | Строка 47: | ||
'''for''' <tex>s \in V:</tex> | '''for''' <tex>s \in V:</tex> | ||
'''for''' <tex>t \in V:</tex> | '''for''' <tex>t \in V:</tex> | ||
− | flow = | + | flow = find_max_flow(s, t) <font color=darkgreen>// максимальный поток {{---}} количество путей из <tex>s</tex> в <tex>t</tex> </font> |
ans = min(ans, flow) | ans = min(ans, flow) | ||
'''return''' ans | '''return''' ans | ||
Строка 63: | Строка 53: | ||
'''Оценка работы''' | '''Оценка работы''' | ||
− | Время работы равно <tex>V^2 \times O(find\_flow)</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> |
== Нахождение вершинной связности == | == Нахождение вершинной связности == | ||
Строка 87: | Строка 77: | ||
==Источники информации== | ==Источники информации== | ||
− | * Харари Ф. | + | * [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.] | ||
+ | |||
+ | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Связность в графах]] | [[Категория: Связность в графах]] |
Версия 23:34, 31 января 2019
Определение: |
Вершинной связностью | графа (англ. vertex-connectivity) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Определение: |
Реберной связностью | графа (англ. edge-connectivity) называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
Содержание
Связь между вершинной, реберной связностью и минимальной степенью вершины
Пускай минимальная степень вершины графа
обозначается буквой . Тогда:Теорема: |
Для любого графа справедливо следующее неравенство: |
Доказательство: |
|
Теорема: |
Для любых натуральных чисел , таких что , существует граф , у которого и |
Доказательство: |
Рассмотрим граф , являющийся объединением двух полных графов и , содержащих вершину. Отметим вершин, принадлежащих подграфу и вершин, принадлежащих подграфу . Добавим в граф ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе и помеченной вершине, лежащей в подграфе , причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:
|
Нахождение реберной связности
Для нахождения реберной связности нужно перебрать все пары вершин , причем такое -связным — максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна .
и , найти количество непересекающихся путей из в и выбрать минимум. Пусть он равен . По утверждению, граф являетсяДля нахождения количества непересекающихся путей из поток (например, алгоритм Эдмондса-Карпа). Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из в , по которым поток неотрицателен и равен (т.к. пропускная способность всех ребер равна ). А значит, если поток равен , то и количество путей равно .
в воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную и найдем максимальныйПсевдокод алгоритма
function disjoint_paths_count(): int ans = INF forfor flow = find_max_flow(s, t) // максимальный поток — количество путей из в ans = min(ans, flow) return ans
Оценка работы
Время работы равно
. При использовании алгоритма Эдмондса-Карпа время равно илиНахождение вершинной связности
Используя аналогичные утверждения и определения для вершинной связности придем к такому же алгоритму с тем отличием, что понадобится искать вершинно-непересекающиеся пути. Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную
. Для этого воспользуемся известным трюком:Разобьем каждую вершину
графа на две вершины и . Все ребра, которые входили в будут входить в . Все ребра, которые выходили из будут выходить из . Так же добавим ребро с пропускной способностью .
После этого для нахождения количества вершинно непересекающихся путей в исходном графе будем искать количество реберно непересекающихся в новом графе.
Тем самым сведя задачу к нахождению реберной связности.