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