Отношение рёберной двусвязности — различия между версиями
Shagal (обсуждение | вклад) (→Реберная двусвязность) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
== Реберная двусвязность == | == Реберная двусвязность == | ||
{{Определение | {{Определение | ||
| Строка 24: | Строка 20: | ||
''Доказательство:'' | ''Доказательство:'' | ||
| − | Пусть из <tex> u </tex> в <tex> v </tex> есть два реберно не пересекающихся пути. Их объединение будет реберно-простым циклом. Обозначим его за <tex> C </tex>. | + | Пусть из <tex> u </tex> в <tex> v </tex> есть два реберно не пересекающихся пути. Назовем эти пути <tex> P_1 </tex> и <tex> P_2 </tex>. Их объединение будет реберно-простым циклом. Обозначим его за <tex> C </tex>. |
| − | Вершина <tex> w </tex> реберно двусвязна с <tex> v | + | Вершина <tex> w </tex> реберно двусвязна с <tex> v </tex>. |
Пусть вершина <tex> a </tex> - пересечение <tex> P_1 </tex> с <tex> C </tex>. | Пусть вершина <tex> a </tex> - пересечение <tex> P_1 </tex> с <tex> C </tex>. | ||
Пусть вершина <tex> b </tex> - пересечение <tex> P_2 </tex> с <tex> C </tex>. | Пусть вершина <tex> b </tex> - пересечение <tex> P_2 </tex> с <tex> C </tex>. | ||
| Строка 32: | Строка 28: | ||
Наличие двух таких реберно не пересекающихся путей очевидно, а значит <tex> u </tex> и <tex> w </tex> реберно двусвязны. | Наличие двух таких реберно не пересекающихся путей очевидно, а значит <tex> u </tex> и <tex> w </tex> реберно двусвязны. | ||
| − | [[Файл:Rcon2.png| | + | [[Файл:Rcon2.png|left|600px|thumb|]] |
}} | }} | ||
| Строка 45: | Строка 41: | ||
[[Отношение вершинной двусвязности]] | [[Отношение вершинной двусвязности]] | ||
| − | == | + | ==См. также== |
| − | [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005 - | + | [http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005 Визуализатор - компоненты двусвязности] |
== Литература == | == Литература == | ||
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 60 с. — ISBN 5-354-00301-6 | * Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 60 с. — ISBN 5-354-00301-6 | ||
Версия 10:31, 28 октября 2011
Содержание
Реберная двусвязность
| Определение: |
| Две вершины и графа называются реберно двусвязными, если между этими вершинами существуют два реберно непересекающихся пути. |
| Теорема: |
Отношение реберной двусвязности является отношением эквивалентности на вершинах. |
| Доказательство: |
|
Пусть - отношение реберной двусвязности. Рефлексивность: (Очевидно) Симметричность: (Очевидно) Транзитивность: и Доказательство: Пусть из в есть два реберно не пересекающихся пути. Назовем эти пути и . Их объединение будет реберно-простым циклом. Обозначим его за . Вершина реберно двусвязна с . Пусть вершина - пересечение с . Пусть вершина - пересечение с . Рассматриваем два пути и таких, что части и идут в разные стороны по относительно часовой стрелки. Наличие двух таких реберно не пересекающихся путей очевидно, а значит и реберно двусвязны. |
Компоненты реберной двусвязности
| Определение: |
| Компонентами реберной двусвязности графа, называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности. |
См. также
Отношение вершинной двусвязности
См. также
Визуализатор - компоненты двусвязности
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 60 с. — ISBN 5-354-00301-6
