Мост, эквивалентные определения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 5 участников)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Мост''' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты реберной двусвязности <tex>G</tex>.  <tex>(1)</tex>
+
'''Мост''' ''(англ. bridge)'' графа <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>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</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>(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 \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>. Противоречие.
+
Тогда между вершинами <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>. Противоречие.
 
}}
 
}}
  
 
== См.также ==
 
== См.также ==
[[Точка сочленения, эквивалентные определения]]
+
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Использование обхода в глубину для поиска мостов]]
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 19:06, 4 сентября 2022

Пусть [math] G [/math] — связный граф.

Определение:
Мост (англ. bridge) графа [math]G[/math] — ребро, соединяющее две компоненты реберной двусвязности [math]G[/math]. [math](1)[/math]


Граф [math]G[/math]


Пример графа с тремя мостами

Эквивалентные определения

Определение:
Мост графа [math]G[/math] — ребро, при удалении которого граф [math]G[/math] становится несвязным. [math](2)[/math]


Определение:
Ребро [math]x[/math] является мостом графа [math]G[/math], если в [math]G[/math] существуют такие вершины [math]u[/math] и [math]v[/math], что любой простой путь между этими вершинами проходит через ребро [math]x.[/math] [math](3)[/math]


Определение:
Ребро [math]x[/math] является мостом графа [math]G[/math], если существует разбиение множества вершин [math]V[/math] на такие множества [math]U[/math] и [math]W[/math], что [math]\forall u \in U[/math] и [math]\forall w \in W[/math] ребро [math]x[/math] принадлежит любому простому пути [math]u \rightsquigarrow w[/math]. [math](4)[/math]


Теорема:
Определения (1), (2), (3) и (4) эквивалентны.
Доказательство:
[math]\triangleright[/math]

[math](1) \Rightarrow (2)[/math] Пусть ребро [math]x[/math] соединяет вершины [math]a[/math] и [math]b[/math]. Пусть граф [math] G - {x} [/math] — связный. Тогда между вершинами [math]a[/math] и [math]b[/math] существует еще один путь, т.е. между вершинами [math]a[/math] и [math]b[/math] существуют два реберно-непересекающихся пути. Но тогда ребро [math]x[/math] не является мостом графа [math]G[/math]. Противоречие.

[math](2) \Rightarrow (4)[/math] В условиях определения (4) пусть существуют такие вершины [math]u[/math] и [math]w[/math], что между ними существует простой путь [math]P: x \notin P[/math]. Но тогда граф [math]G - {x}[/math] — связный. Противоречие.

[math](4) \Rightarrow (3)[/math] Возьмем [math]\forall u \in U[/math] и [math]\forall w \in W [/math]. Тогда [math]\forall[/math] простой путь [math]u \rightsquigarrow w[/math] содержит ребро [math]x[/math]. Утверждение доказано

[math](3) \Rightarrow (1)[/math] Пусть [math](a, b) = x[/math]. Пусть ребро [math]x[/math] не является мостом по определению (1).

Тогда между вершинами [math]a[/math] и [math]b[/math] есть простой путь [math]P : P \cap x = \varnothing[/math]. Составим такой путь [math]Q[/math], что [math]Q = ((u \rightsquigarrow a ) \circ P \circ (b \rightsquigarrow w)) [/math]. Сделаем путь [math]Q[/math] простым. Получим простой путь [math](u \rightsquigarrow w)[/math], не проходящий по ребру [math]x[/math]. Противоречие.
[math]\triangleleft[/math]

См.также

Источники информации

  • Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)