Отношение вершинной двусвязности — различия между версиями
| Строка 17: | Строка 17: | ||
'''Транзитивность:''' | '''Транзитивность:''' | ||
| − | + | (пока не написано) | |
| − | |||
| − | |||
| − | |||
}} | }} | ||
| Строка 40: | Строка 37: | ||
Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности. | Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности. | ||
}} | }} | ||
| + | |||
| + | |||
| + | ==Литература== | ||
| + | * Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009 | ||
Версия 07:09, 14 октября 2010
Вершинная двусвязность
| Определение: |
| Два ребра графа называются вершинно двусвязными, если существует два вершинно непересекающихся пути, попарно соединяющие их концы. |
| Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
| Доказательство: |
|
Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. Коммутативность: Следует из симметричности определения. Транзитивность: (пока не написано) |
Замечание. Рассмотрим следующее определение: вершины и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
Блоки
| Определение: |
| Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества концов ребер из соответствующих классов. |
Точки сочленения
| Определение: |
| Точка сочленения графа - вершина, принадлежащая как минимум двум блокам . |
| Определение: |
| Точка сочленения графа - вершина, при удалении которой в увеличивается число компонент связности. |
Литература
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
