Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 78 промежуточных версий 9 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | + | '''Вершинной связностью''' <tex>\kappa</tex> графа <tex>G</tex> (англ. ''vertex-connectivity'') называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. | |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | + | '''Реберной связностью''' <tex>\lambda</tex> графа <tex>G</tex> (англ. ''edge-connectivity'') называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу. | |
}} | }} | ||
+ | == Связь между вершинной, реберной связностью и минимальной степенью вершины == | ||
+ | Пускай минимальная степень вершины графа <tex>G</tex> обозначается буквой <tex>\delta</tex>. Тогда: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Для любого графа | + | Для любого графа <tex>G</tex> справедливо следующее неравенство: <tex>\kappa \leqslant \lambda \leqslant \delta </tex> |
− | |||
|proof= | |proof= | ||
− | + | [[Файл:Ver_ed_coh_1.png|thumb|right|150px|Полный граф. <tex> \lambda = \delta = \kappa = 4</tex>]] | |
− | + | # Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \leqslant \delta </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> \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= | ||
− | Для любых натуральных чисел a, b, c, таких что a | + | Для любых натуральных чисел <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>\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>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>\kappa \geqslant a</tex>. Однако если удалить из графа <tex>G</tex> помеченные вершины его подграфа <tex>G_2</tex>, то граф <tex>G</tex> потеряет связность. Значит, <tex>\kappa = a</tex>. | ||
+ | # Аналогично рассуждению пункта 2, легко убедится, что <tex>\lambda = b</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>. | ||
+ | |||
+ | ''' Псевдокод алгоритма ''' | ||
+ | '''function''' disjoint_paths_count(): '''int''' | ||
+ | ans = INF | ||
+ | '''for''' <tex>s \in V:</tex> | ||
+ | '''for''' <tex>t \in V:</tex> | ||
+ | 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\_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>. | ||
+ | |||
+ | [[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]] | ||
+ | <br clear="all"/> | ||
+ | |||
+ | После этого для нахождения количества вершинно непересекающихся путей в исходном графе будем искать количество реберно непересекающихся в новом графе. | ||
+ | |||
+ | Тем самым сведя задачу к нахождению реберной связности. | ||
+ | |||
+ | ==См. также== | ||
+ | |||
+ | *[[Теорема Менгера]] | ||
+ | *[[Алгоритм Эдмондса-Карпа]] | ||
+ | *[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 Википедия {{---}} Теорема Роббинса] | ||
+ | |||
+ | ==Источники информации== | ||
+ | |||
+ | * [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.] | ||
+ | |||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Связность в графах]] |
Текущая версия на 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
Оценка работы
Время работы равно
. При использовании алгоритма Эдмондса-Карпа время равно илиНахождение вершинной связности
Используя аналогичные утверждения и определения для вершинной связности придем к такому же алгоритму с тем отличием, что понадобится искать вершинно-непересекающиеся пути. Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную
. Для этого воспользуемся известным трюком:Разобьем каждую вершину
графа на две вершины и . Все ребра, которые входили в будут входить в . Все ребра, которые выходили из будут выходить из . Так же добавим ребро с пропускной способностью .
После этого для нахождения количества вершинно непересекающихся путей в исходном графе будем искать количество реберно непересекающихся в новом графе.
Тем самым сведя задачу к нахождению реберной связности.