Отношение вершинной двусвязности — различия между версиями
Creep (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 23 промежуточные версии 9 участников) | |||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''', если существуют вершинно непересекающиеся пути, соединяющие их концы. | + | Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''' (англ. ''vertex biconnected''), если существуют вершинно непересекающиеся пути, соединяющие их концы. |
}} | }} | ||
Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле. | Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле. | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | '''Блоками''' (англ. ''block''), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов. | ||
| + | }} | ||
{{Теорема | {{Теорема | ||
| Строка 11: | Строка 15: | ||
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. | Отношение вершинной двусвязности является отношением эквивалентности на ребрах. | ||
|proof= | |proof= | ||
| − | [[Файл: | + | [[Файл: Vertex_biconnected.png|370px|thumb|right|К доказательству транзитивности]] |
'''Рефлексивность:''' | '''Рефлексивность:''' | ||
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. | В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. | ||
| − | + | ||
'''Симметричность:''' | '''Симметричность:''' | ||
Следует из симметричности определения. | Следует из симметричности определения. | ||
| − | + | ||
'''Транзитивность:''' | '''Транзитивность:''' | ||
| − | Пусть имеем ребра: <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>. |
}} | }} | ||
| − | + | ||
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Точки сочленения== | ==Точки сочленения== | ||
| Строка 34: | Строка 32: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | '''Точка сочленения''' (англ. ''articulation points'') графа <tex>G</tex> {{---}} вершина, принадлежащая как минимум двум блокам <tex>G</tex>. | |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | '''Точка сочленения''' графа <tex>G</tex> {{---}} вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности. | |
}} | }} | ||
| − | == | + | == См. также == |
| + | * [[Отношение рёберной двусвязности]] | ||
| + | |||
| + | ==Источники информации== | ||
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009 | * Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009 | ||
| + | * [[wikipedia:ru:Двусвязный_граф | Википедия {{---}} Двусвязный граф]] | ||
| − | + | [[Категория:Алгоритмы и структуры данных]] | |
| − | + | [[Категория:Связность в графах]] | |
Текущая версия на 19:33, 4 сентября 2022
Вершинная двусвязность
| Определение: |
| Два ребра графа называются вершинно двусвязными (англ. vertex biconnected), если существуют вершинно непересекающиеся пути, соединяющие их концы. |
Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.
| Определение: |
| Блоками (англ. block), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин — множества всевозможных концов ребер из соответствующих классов. |
| Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
| Доказательство: |
|
Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. Симметричность: Следует из симметричности определения. Транзитивность: Пусть имеем ребра: вершинно двусвязно с , вершинно двусвязно с , при этом все они различны. Ребра и лежат на вершинно простом цикле . Будем считать, что существуют непересекающиеся пути , (ситуация, когда они идут наоборот, разбирается аналогично). Пусть — первая вершина на , лежащая также на , — первая вершина на , лежащая на . Проделав пути от до и от до , далее пойдем по циклу в нужные (различные) стороны, чтобы достичь и . То есть вершинно двусвязно с . |
Замечание. Рассмотрим следующее определение: вершины и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
Точки сочленения
| Определение: |
| Точка сочленения (англ. articulation points) графа — вершина, принадлежащая как минимум двум блокам . |
| Определение: |
| Точка сочленения графа — вершина, при удалении которой в увеличивается число компонент связности. |
См. также
Источники информации
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
- Википедия — Двусвязный граф
