Редактирование: Мост, эквивалентные определения
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Мост' | + | '''Мост''' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты реберной двусвязности <tex>G</tex>. <tex>(1)</tex> |
}} | }} | ||
| Строка 34: | Строка 34: | ||
<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>(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>(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>(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>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1). | ||
| − | Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \ | + | Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \land 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>. Противоречие. |
}} | }} | ||
== См.также == | == См.также == | ||
| − | + | [[Точка сочленения, эквивалентные определения]] | |
| − | |||
==Источники информации== | ==Источники информации== | ||
