Вершинная двусвязность
| Определение: |
| Два ребра графа называются вершинно двусвязными, если они лежат на некотором вершинно простом цикле. |
| Теорема: |
Отношение вершинной двусвязности является отношением эквивалентности на ребрах. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рефлексивность:
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
Симметричность:
Следует из симметричности определения.
Транзитивность:
Набросок доказательства (будет улучшаться):
Пусть имеем ребра [math]ef[/math] вершинно двусвязно с [math]cd[/math], [math]cd[/math] вершинно двусвязно с [math]ab[/math]. Ребра [math]ef[/math] и [math]cd[/math] лежат на вершинно простом цикле [math]C[/math]. Будем считать, что существуют непересекающиеся пути [math]P : a \leadsto c[/math], [math]Q : b \leadsto d[/math] (ситуация, когда они идут наоборот, разбирается аналогично). Пусть [math]x[/math] - первая вершина на [math]P[/math], лежащая также на [math]C[/math], [math]y[/math] - первая вершина на [math]Q[/math], лежащая на [math]C[/math]. Проделав пути от [math]a[/math] до [math]x[/math] и от [math]b[/math] до [math]y[/math], далее пойдем по циклу [math]C[/math] в нужные (различные) стороны, чтобы достичь [math]e[/math] и [math]f[/math]. (Лучше нарисовать картинку.) |
| [math]\triangleleft[/math] |
Замечание. Рассмотрим следующее определение: вершины [math]u[/math] и [math]v[/math] называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
