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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
−
Пусть <math> G </math> - связный граф.
+
Пусть <tex> G </tex> - связный граф.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(1) Мост графа <math>G</math> - ребро, соединяющее как минимум две компоненты реберной двусвязности <math>G</math>.
+
(1) Мост графа <tex>G</tex> - ребро, соединяющее как минимум две компоненты реберной двусвязности <tex>G</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(2) Мост графа <math>G</math> - ребро, при удалении которого граф <math>G</math> становится несвязным.
+
(2) Мост графа <tex>G</tex> - ребро, при удалении которого граф <tex>G</tex> становится несвязным.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
(3) Ребро <math>x</math> является мостом графа <math>G</math>, если в <math>G</math> существуют такие вершины <math>u</math> и <math>v</math>, что любой простой путь между этими вершинами проходит через ребро <math>x.</math>
+
(3) Ребро <tex>x</tex> является мостом графа <tex>G</tex>, если в <tex>G</tex> существуют такие вершины <tex>u</tex> и <tex>v</tex>, что любой простой путь между этими вершинами проходит через ребро <tex>x.</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>
+
(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>
 
}}
 
}}
  
Строка 23: Строка 23:
 
|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>. Противоречие.
+
<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>(2) \Rightarrow (4)</math> В условиях определения (4) пусть существует такие вершины <math>u</math> и <math>w</math>, что между ними существует простой путь <math>P: x \notin P</math>. Но тогда граф <math>G - {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>(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>(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>(3) \Rightarrow (1)</math> Пусть <math>(a, b) = x</math>. Пусть ребро <math>x</math> не является мостом по определению (1).
+
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).
−
Тогда между вершинами <math>a</math> и <math>b</math> есть простой путь <math>P = (a \rightsquigarrow b) : 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>a</tex> и <tex>b</tex> есть простой путь <tex>P = (a \rightsquigarrow b) : P \land x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow w) \lor P) - x</tex>. Заметим, что он будет без разрывов. Сделаем путь <tex>Q</tex> простым (пройти по пути <tex>Q</tex>, удаляя все повторяющиеся вершины). Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.
 
}}
 
}}
  
 
== См.также ==
 
== См.также ==
 
[[Точка сочленения, эквивалентные определения]]
 
[[Точка сочленения, эквивалентные определения]]

Версия 23:53, 13 октября 2010

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

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


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


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


Определение:
(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]


Теорема:
Определения (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 = (a \rightsquigarrow b) : P \land x = \varnothing[/math]. Составим такой путь [math]Q[/math], что [math]Q = ((u \rightsquigarrow w) \lor P) - x[/math]. Заметим, что он будет без разрывов. Сделаем путь [math]Q[/math] простым (пройти по пути [math]Q[/math], удаляя все повторяющиеся вершины). Получим простой путь [math](u \rightsquigarrow w)[/math], не проходящий по ребру [math]x[/math]. Противоречие.
[math]\triangleleft[/math]

См.также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Мост,_эквивалентные_определения&oldid=3878»