Изменения

Перейти к: навигация, поиск

Отношение вершинной двусвязности

161 байт добавлено, 05:16, 25 января 2011
Отмена правки 7648 участника Igor buzhinsky (обсуждение)
{{В разработке}}
<br>
==Вершинная двусвязность==
{{Определение
<br>
'''Транзитивность:'''
Набросок доказательства (будет улучшаться):Пусть имеем ребра <tex>ef</tex> вершинно двусвязно с <tex>cd</tex>, <tex>cd</tex> вершинно двусвязно с <tex>ab</tex>. Ребра <tex>ef</tex> и <tex>cd</tex> лежат на вершинно простом цикле <tex>C</tex>. Будем считать, что существуют непересекающиеся пути <tex>P : a \leadsto c</tex>, <tex>Q : b \leadsto d</tex> (ситуация, когда они идут наоборот, разбирается аналогично). Пусть <tex>x</tex> - первая вершина на <tex>P</tex>, лежащая также на <tex>C</tex>, <tex>y</tex> - первая вершина на <tex>Q</tex>, лежащая на <tex>C</tex>Пока не написано. Проделав пути от <tex>a</tex> до <tex>x</tex> и от <tex>b</tex> до <tex>y</tex>, далее пойдем по циклу <tex>C</tex> в нужные (различные) стороныВы можете помочь статье, чтобы достичь <tex>e</tex> и <tex>f</tex>. (Лучше нарисовать картинкунаписав доказательство.)
}}
<br>
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
 
==Блоки==
{{Определение
|definition=
Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества всевозможных концов ребер из соответствующих классов.
}}
 
==Точки сочленения==
{{main|Точка сочленения, эквивалентные определения}}
{{Определение
|definition=
Точка сочленения графа <tex>G</tex> - вершина, принадлежащая как минимум двум блокам <tex>G</tex>.
}}
{{Определение
|definition=
Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.
}}
 
== См. также ==
* [[Отношение реберной двусвязности]]
322
правки

Навигация