Изменения

Перейти к: навигация, поиск

Мост, эквивалентные определения

415 байт добавлено, 14:14, 30 сентября 2021
Добавил ссылку на статью "Использование обхода в глубину для поиска мостов"
Пусть <tex> G </tex> {{- --}} связный граф.
{{Определение
|definition=
'''Мост''' ''(1англ. bridge) Мост '' графа <tex>G</tex> {{- --}} ребро, соединяющее как минимум две компоненты [[Отношение рёберной двусвязности|реберной двусвязности ]] <tex>G</tex>. <tex>(1)</tex>
}}
 
 
[[Файл:Bridge_1.png|left|thumb|240px|Граф <tex>G</tex>]]
<br clear="all"/>
 
Пример графа с тремя мостами
 
==Эквивалентные определения==
{{Определение
|definition=
(2) Мост графа <tex>G</tex> {{--- }} ребро, при удалении которого граф <tex>G</tex> становится несвязным. <tex>(2)</tex>
}}
{{Определение
|definition=
(3) Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если в <tex>G</tex> существуют такие вершины <tex>u</tex> и <tex>v</tex>, что любой простой путь между этими вершинами проходит через ребро <tex>x.</tex> <tex>(3)</tex>
}}
{{Определение
|definition=
(4) Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если существует разбиение множества вершин <tex>V</tex> на такие множества <tex>U</tex> и <tex>W</tex>, что <tex>\forall u \in U</tex> и <tex>\forall w \in W</tex> ребро <tex>x</tex> принадлежит любому простому пути <tex>u \rightsquigarrow w</tex>. <tex>(4)</tex>
}}
|statement = Определения (1), (2), (3) и (4) эквивалентны.
|proof =
Пусть <tex>A </tex> и <tex> B </tex> - пути. Тогда пересечение путей <tex>A \land B : (a, b) \in A \land B \Rightarrow (a, b) \in A \land (a, b) \in B</tex>
<tex>(1) \Rightarrow (2)</tex> Пусть ребро <tex>x</tex> соединяет вершины <tex>a</tex> и <tex>b</tex>. Пусть граф <tex> G - {x} </tex> {{- --}} связный. Тогда между вершинами <tex>a</tex> и <tex>b</tex> существует еще один путь, т.е. между вершинами <tex>a</tex> и <tex>b</tex> существуют два реберно не пересекающихся -непересекающихся пути. Но тогда ребро <tex>x</tex> не является мостом графа <tex>G</tex>. Противоречие.
<tex>(2) \Rightarrow (4)</tex> В условиях определения (4) пусть существует существуют такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{- --}} связный. Противоречие.
<tex>(4) \Rightarrow (3)</tex> Возьмем <tex>\forall u \in U</tex> и <tex>\forall w \in W </tex>. Тогда <tex>\forall</tex> простой путь <tex>u \rightsquigarrow w</tex> содержит ребро <tex>x</tex>. Утверждение доказано
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).
Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \land cap x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow a ) \circ P \circ (b \rightsquigarrow w )</tex> o <tex> P) - x</tex>. Сделаем путь <tex>Q</tex> [[Теорема о существовании простого пути в случае существования пути|простым (пройти по пути <tex>Q</tex>, удаляя все повторяющиеся вершины)]]. Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.
}}
== Литература См.также ==* Харари Ф. Теория графов.[http://reslib.com/book/985[Точка сочленения, эквивалентные определения]]* [[Использование обхода в глубину для поиска мостов]] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
== См.также Источники информации==* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.) [[Точка сочленения, эквивалентные определенияКатегория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]
Анонимный участник

Навигация