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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 24: Строка 24:
 
|proof =  
 
|proof =  
  
<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> - связный. Противоречие.

Версия 22:50, 23 января 2011

Пусть [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 : P \land 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]

Литература

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

См.также

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