http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=77.234.193.2&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T15:20:14ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%BE%D1%81%D1%82,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=81171Мост, эквивалентные определения2021-09-30T11:14:09Z<p>77.234.193.2: Добавил ссылку на статью "Использование обхода в глубину для поиска мостов"</p>
<hr />
<div>Пусть <tex> G </tex> {{---}} связный граф.<br />
{{Определение<br />
|definition=<br />
'''Мост''' ''(англ. bridge)'' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты [[Отношение рёберной двусвязности|реберной двусвязности]] <tex>G</tex>. <tex>(1)</tex><br />
}}<br />
<br />
<br />
[[Файл:Bridge_1.png|left|thumb|240px|Граф <tex>G</tex>]]<br />
<br clear="all"/><br />
<br />
Пример графа с тремя мостами<br />
<br />
==Эквивалентные определения==<br />
<br />
{{Определение<br />
|definition=<br />
Мост графа <tex>G</tex> {{---}} ребро, при удалении которого граф <tex>G</tex> становится несвязным. <tex>(2)</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если в <tex>G</tex> существуют такие вершины <tex>u</tex> и <tex>v</tex>, что любой простой путь между этими вершинами проходит через ребро <tex>x.</tex> <tex>(3)</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Ребро <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><br />
}}<br />
<br />
{{Теорема<br />
|statement = Определения (1), (2), (3) и (4) эквивалентны.<br />
|proof = <br />
<br />
<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>. Противоречие.<br />
<br />
<tex>(2) \Rightarrow (4)</tex> В условиях определения (4) пусть существуют такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{---}} связный. Противоречие.<br />
<br />
<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>. Утверждение доказано<br />
<br />
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).<br />
Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \cap x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow a ) \circ P \circ (b \rightsquigarrow w)) </tex>. Сделаем путь <tex>Q</tex> [[Теорема о существовании простого пути в случае существования пути|простым]]. Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.<br />
}}<br />
<br />
== См.также ==<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
<br />
==Источники информации==<br />
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>77.234.193.2http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%BE%D1%81%D1%82,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=81170Мост, эквивалентные определения2021-09-30T11:12:19Z<p>77.234.193.2: Добавил ссылку на статью об отношении рёберной двусвязности</p>
<hr />
<div>Пусть <tex> G </tex> {{---}} связный граф.<br />
{{Определение<br />
|definition=<br />
'''Мост''' ''(англ. bridge)'' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты [[Отношение рёберной двусвязности|реберной двусвязности]] <tex>G</tex>. <tex>(1)</tex><br />
}}<br />
<br />
<br />
[[Файл:Bridge_1.png|left|thumb|240px|Граф <tex>G</tex>]]<br />
<br clear="all"/><br />
<br />
Пример графа с тремя мостами<br />
<br />
==Эквивалентные определения==<br />
<br />
{{Определение<br />
|definition=<br />
Мост графа <tex>G</tex> {{---}} ребро, при удалении которого граф <tex>G</tex> становится несвязным. <tex>(2)</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если в <tex>G</tex> существуют такие вершины <tex>u</tex> и <tex>v</tex>, что любой простой путь между этими вершинами проходит через ребро <tex>x.</tex> <tex>(3)</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Ребро <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><br />
}}<br />
<br />
{{Теорема<br />
|statement = Определения (1), (2), (3) и (4) эквивалентны.<br />
|proof = <br />
<br />
<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>. Противоречие.<br />
<br />
<tex>(2) \Rightarrow (4)</tex> В условиях определения (4) пусть существуют такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{---}} связный. Противоречие.<br />
<br />
<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>. Утверждение доказано<br />
<br />
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).<br />
Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \cap x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow a ) \circ P \circ (b \rightsquigarrow w)) </tex>. Сделаем путь <tex>Q</tex> [[Теорема о существовании простого пути в случае существования пути|простым]]. Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.<br />
}}<br />
<br />
== См.также ==<br />
* [[Точка сочленения, эквивалентные определения]]<br />
<br />
==Источники информации==<br />
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>77.234.193.2