Отношение рёберной двусвязности — различия между версиями
(Новая страница: «== Реберная двусвязность == {{Определение |definition = Две вершины <math>U, V</math> графа называются '''р…») |
|||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | Две вершины <math>U | + | Две вершины <math>U</math> и <math> V</math> графа <math>G</math> называются '''реберно двусвязными''', если между этими вершинами существуют два реберно непересекающихся пути. |
| + | }} | ||
| + | |||
| + | {{Теорема | ||
| + | |statement= | ||
| + | Отношение реберной двусвязности является отношением эквивалентности на вершинах. | ||
| + | |proof= | ||
| + | Пусть <math>R</math> - отношение реберной двусвязности. | ||
| + | '''Рефлексивность:''' <math>(u, u)\in R. </math> (Очевидно) | ||
| + | |||
| + | '''Коммутативность:''' <math>(u, v)\in R \Rightarrow (v, u)\in R. </math> (Очевидно) | ||
| + | '''Транзитивность:''' <math>(u, v)\in R </math> и <math>(v, w)\in R \Rightarrow (u, w)\in R. </math> | ||
}} | }} | ||
Версия 20:19, 1 октября 2010
Реберная двусвязность
| Определение: |
| Две вершины и графа называются реберно двусвязными, если между этими вершинами существуют два реберно непересекающихся пути. |
| Теорема: |
Отношение реберной двусвязности является отношением эквивалентности на вершинах. |
| Доказательство: |
|
Пусть - отношение реберной двусвязности. Рефлексивность: (Очевидно) Коммутативность: (Очевидно) Транзитивность: и |
