Отношение вершинной двусвязности — различия между версиями
(→Блоки) |
(→Вершинная двусвязность) |
||
| Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''', если | + | Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''', если они лежат на некотором простом цикле. |
}} | }} | ||
| − | + | <br> | |
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| Строка 14: | Строка 14: | ||
'''Рефлексивность:''' | '''Рефлексивность:''' | ||
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. | В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. | ||
| − | + | <br> | |
'''Коммутативность:''' | '''Коммутативность:''' | ||
Следует из симметричности определения. | Следует из симметричности определения. | ||
| − | + | <br> | |
'''Транзитивность:''' | '''Транзитивность:''' | ||
(пока не написано) | (пока не написано) | ||
}} | }} | ||
| − | + | <br> | |
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ||
Версия 08:33, 15 января 2011
Эта статья находится в разработке!
Вершинная двусвязность
| Определение: |
| Два ребра графа называются вершинно двусвязными, если они лежат на некотором простом цикле. |
| Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
| Доказательство: |
|
Рефлексивность:
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
|
Замечание. Рассмотрим следующее определение: вершины и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
Блоки
| Определение: |
| Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества всевозможных концов ребер из соответствующих классов. |
Точки сочленения
| Определение: |
| Точка сочленения графа - вершина, принадлежащая как минимум двум блокам . |
| Определение: |
| Точка сочленения графа - вершина, при удалении которой в увеличивается число компонент связности. |
