Отношение вершинной двусвязности — различия между версиями
(→Вершинная двусвязность) |
|||
Строка 19: | Строка 19: | ||
'''Транзитивность:''' | '''Транзитивность:''' | ||
− | Пусть имеем ребра: <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>. | + | Пусть имеем ребра: <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>. То есть <tex>ef</tex> вершинно двусвязно с <tex>ab</tex>. |
}} | }} | ||
Версия 16:53, 8 мая 2012
Вершинная двусвязность
Определение: |
Два ребра графа называются вершинно двусвязными, если существуют вершинно непересекающиеся пути, соединяющие их концы. |
Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.
Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
Доказательство: |
Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. Симметричность: Следует из симметричности определения. Транзитивность: Пусть имеем ребра: вершинно двусвязно с , вершинно двусвязно с , при этом все они различны. Ребра и лежат на вершинно простом цикле . Будем считать, что существуют непересекающиеся пути , (ситуация, когда они идут наоборот, разбирается аналогично). Пусть — первая вершина на , лежащая также на , — первая вершина на , лежащая на . Проделав пути от до и от до , далее пойдем по циклу в нужные (различные) стороны, чтобы достичь и . То есть вершинно двусвязно с . |
Замечание. Рассмотрим следующее определение: вершины
и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.Блоки
Определение: |
Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин — множества всевозможных концов ребер из соответствующих классов. |
Точки сочленения
Определение: |
Точка сочленения графа | — вершина, принадлежащая как минимум двум блокам .
Определение: |
Точка сочленения графа | — вершина, при удалении которой в увеличивается число компонент связности.
Литература
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009