Отношение вершинной двусвязности — различия между версиями
(Отмена правки 7648 участника Igor buzhinsky (обсуждение)) |
|||
| Строка 1: | Строка 1: | ||
| + | {{В разработке}} | ||
| + | <br> | ||
==Вершинная двусвязность== | ==Вершинная двусвязность== | ||
{{Определение | {{Определение | ||
| Строка 17: | Строка 19: | ||
<br> | <br> | ||
'''Транзитивность:''' | '''Транзитивность:''' | ||
| − | + | (Пока не написано. Вы можете помочь статье, написав доказательство.) | |
| − | |||
}} | }} | ||
<br> | <br> | ||
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ||
| + | |||
| + | ==Блоки== | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества всевозможных концов ребер из соответствующих классов. | ||
| + | }} | ||
| + | |||
| + | ==Точки сочленения== | ||
| + | {{main|Точка сочленения, эквивалентные определения}} | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | Точка сочленения графа <tex>G</tex> - вершина, принадлежащая как минимум двум блокам <tex>G</tex>. | ||
| + | }} | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности. | ||
| + | }} | ||
| + | |||
| + | == См. также == | ||
| + | * [[Отношение реберной двусвязности]] | ||
Версия 05:16, 25 января 2011
Эта статья находится в разработке!
Вершинная двусвязность
| Определение: |
| Два ребра графа называются вершинно двусвязными, если они лежат на некотором вершинно простом цикле. |
| Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
| Доказательство: |
|
Рефлексивность:
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
|
Замечание. Рассмотрим следующее определение: вершины и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
Блоки
| Определение: |
| Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества всевозможных концов ребер из соответствующих классов. |
Точки сочленения
| Определение: |
| Точка сочленения графа - вершина, принадлежащая как минимум двум блокам . |
| Определение: |
| Точка сочленения графа - вершина, при удалении которой в увеличивается число компонент связности. |
