Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями
Vsklamm (обсуждение | вклад) (цвет комментов) |
(→Связь между вершинной, реберной связностью и минимальной степенью вершины) |
||
Строка 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>. |
Версия 12:52, 24 декабря 2018
Определение: |
Вершинной связностью | графа (англ. vertex-connectivity) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Определение: |
Реберной связностью | графа (англ. edge-connectivity) называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
Содержание
Связь между вершинной, реберной связностью и минимальной степенью вершины
Пускай минимальная степень вершины графа
обозначается буквой . Тогда:Теорема: |
Для любого графа справедливо следующее неравенство: |
Доказательство: |
|
Теорема: |
Для любых натуральных чисел , таких что , существует граф , у которого и |
Доказательство: |
Рассмотрим граф , являющийся объединением двух полных графов и , содержащих вершину. Отметим вершин, принадлежащих подграфу и вершин, принадлежащих подграфу . Добавим в граф ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе и помеченной вершине, лежащей в подграфе , причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:
|
Нахождение реберной связности
Для нахождения реберной связности нужно перебрать все пары вершин , причем такое -связным - максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна .
и , найти количество непересекающихся путей из в и выбрать минимум. Пусть он равен . По утверждению, граф являетсяДля нахождения количества непересекающихся путей из поток. Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из в , по которым поток неотрицателен и равен (т.к. пропускная способность всех ребер равна ). А значит, если поток равен , то и количество путей равно .
в воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную и найдем максимальныйПсевдокод алгоритма
function disjoint_paths_count(): int ans = INF forfor flow = find_flow(s, t) // максимальный поток - количество путей из в ans = min(ans, flow) return ans
Оценка работы
Время работы равно алгоритма Эдмондса-Карпа время равно или
. При использованииНахождение вершинной связности
Используя аналогичные утверждения и определения для вершинной связности придем к такому же алгоритму с тем отличием, что понадобится искать вершинно-непересекающиеся пути. Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную
. Для этого воспользуемся известным трюком:Разобьем каждую вершину
графа на две вершины и . Все ребра, которые входили в будут входить в . Все ребра, которые выходили из будут выходить из . Так же добавим ребро с пропускной способностью .
После этого для нахождения количества вершинно непересекающихся путей в исходном графе будем искать количество реберно непересекающихся в новом графе.
Тем самым сведя задачу к нахождению реберной связности.