Отношение вершинной двусвязности

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Вершинная двусвязность

Определение:

Два ребра графа называются вершинно двусвязными (англ. vertex biconnected), если существуют вершинно непересекающиеся пути, соединяющие их концы.

Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.

Определение:

Блоками (англ. block), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин — множества всевозможных концов ребер из соответствующих классов.

Теорема:

Отношение вершинной двусвязности является отношением эквивалентности на ребрах.

Доказательство:

[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]ef[/math] вершинно двусвязно с [math]ab[/math].

[math]\triangleleft[/math]

Замечание. Рассмотрим следующее определение: вершины [math]u[/math] и [math]v[/math] называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.

Точки сочленения

Определение:

Точка сочленения (англ. articulation points) графа [math]G[/math] — вершина, принадлежащая как минимум двум блокам [math]G[/math].

Определение:

Точка сочленения графа [math]G[/math] — вершина, при удалении которой в [math]G[/math] увеличивается число компонент связности.

См. также

• Отношение рёберной двусвязности

Источники информации

• Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
• Википедия — Двусвязный граф