Граф блоков-точек сочленения

НЕТ ВОЙНЕ

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

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

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

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

Пусть граф [math]G[/math] связен. Обозначим [math]A_1...A_n[/math] — блоки, а [math]a_1...a_m[/math] — точки сочленения [math]G[/math]. Построим двудольный граф [math]T[/math], поместив [math]A_1...A_n[/math] и [math]a_1...a_m[/math] в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф [math]T[/math] называют графом блоков-точек сочленения (англ. block cutpoint graph) графа [math]G[/math].

Граф [math]G[/math]

Граф [math]T[/math]

Лемма:

В определении, приведенном выше, [math]T[/math] — дерево.

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

[math]\triangleright[/math]

Достаточно показать, что в [math]T[/math] нет циклов. Пусть [math]A_i, a_k, A_j: a_k \in A_i, A_j[/math] — последовательные вершины [math]T[/math], лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая [math]A_i[/math] и [math]A_j[/math] и не содержащая [math]a_k[/math]. По ней можно проложить путь в [math]G[/math] (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине [math]a_k[/math], получив цикл. Получается, что некоторые рёбра из [math]A_i[/math] и [math]A_j[/math] принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках.

[math]\triangleleft[/math]

См. также

• Граф компонент реберной двусвязности

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

• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5