Покрытие рёбер графа путями
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Теорема: |
Пусть — связный граф, в котором вершин имеют нечётную степень. Тогда множество рёбер можно покрыть рёберно-простыми путями. |
| Доказательство: |
|
Рассмотрим связный граф который содержит вершин, имеющих нечётную степень. Докажем, что его можно покрыть рёберно-простыми путями. Добавим в граф рёбер, соединив попарно вершины, имеющие нечётные степени, и получим связный граф все вершины которого имеют чётную степень. Такой граф удовлетворяет критерию эйлеровости и содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него добавленных ребер Цикл распадётся на путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым. |
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
