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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 11 участников)
Строка 1: Строка 1:
−
Пусть <math> G </math> - связный граф.
+
Пусть <tex> G </tex> {{---}} связный граф.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(1) Мост графа <math>G</math> - ребро, соединяющее как минимум две компоненты реберной двусвязности <math>G</math>.
+
'''Мост''' ''(англ. bridge)'' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты [[Отношение рёберной двусвязности|реберной двусвязности]] <tex>G</tex>. <tex>(1)</tex>
 
}}
 
}}
 +
 +
 +
[[Файл:Bridge_1.png|left|thumb|240px|Граф <tex>G</tex>]]
 +
<br clear="all"/>
 +
 +
Пример графа с тремя мостами
 +
 +
==Эквивалентные определения==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(2) Мост графа <math>G</math> - ребро, при удалении которого граф <math>G</math> становится несвязным.
+
Мост графа <tex>G</tex> {{---}} ребро, при удалении которого граф <tex>G</tex> становится несвязным. <tex>(2)</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(3) Ребро <math>x</math> является мостом графа <math>G</math>, если в <math>G</math> существуют такие вершины <math>u</math> и <math>v</math>, что любой простой путь между этими вершинами проходит через ребро <math>x.</math>
+
Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если в <tex>G</tex> существуют такие вершины <tex>u</tex> и <tex>v</tex>, что любой простой путь между этими вершинами проходит через ребро <tex>x.</tex>  <tex>(3)</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(4) Ребро <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>
+
Ребро <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>
 
}}
 
}}
  
Строка 23: Строка 31:
 
|statement = Определения (1), (2), (3) и (4) эквивалентны.
 
|statement = Определения (1), (2), (3) и (4) эквивалентны.
 
|proof =  
 
|proof =  
−
<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> - связный. Противоречие.
+
<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>. Противоречие.
  
−
<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>. Утверждение доказано
+
<tex>(2) \Rightarrow (4)</tex> В условиях определения (4) пусть существуют такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{---}} связный. Противоречие.
  
−
<math>(3) \Rightarrow (1)</math> Пусть <math>(a, b) = x</math>. Пусть ребро <math>x</math> не является мостом по определению (1).
+
<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>. Утверждение доказано
−
Тогда между вершинами <math>a</math> и <math>b</math> есть простой путь <math>P : P \and x = \varnothing</math>. Составим такой путь <math>Q</math>, что <math>Q = ((u \rightsquigarrow w) \or P) - x</math>. Заметим, что он будет без разрывов. Сделаем путь <math>Q</math> простым (пройти по пути <math>Q</math>, удаляя все повторяющиеся вершины). Получим простой путь <math>(u \rightsquigarrow w)</math>, не проходящий по ребру <math>x</math>. Противоречие.
+
 
 +
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).
 +
Тогда между вершинами <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>. Противоречие.
 
}}
 
}}
  
 
== См.также ==
 
== См.также ==
−
[[Точка сочленения, эквивалентные определения]]
+
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Использование обхода в глубину для поиска мостов]]
 +
 
 +
==Источники информации==
 +
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Связность в графах]]

Текущая версия на 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 с.)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Мост,_эквивалентные_определения&oldid=84460»