Лемма о белых путях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =

Текущая версия на 19:28, 4 сентября 2022

Лемма:
Не существует такого момента выполнения поиска в глубину, в который бы существовало ребро из черной вершины в белую.
Доказательство:
[math]\triangleright[/math]
Пусть в процессе выполнения процедуры [math]dfs[/math] нашлось ребро из черной вершины [math]v[/math] в белую вершину [math]u[/math]. Рассмотрим момент времени, когда мы запустили [math]dfs(v)[/math]. В этот момент вершина [math]v[/math] была перекрашена из белого в серый, а вершина [math]u[/math] была белая. Далее в ходе выполнения алгоритма будет запущен [math]dfs(u)[/math], поскольку обход в глубину обязан посетить все белые вершины, в которые есть ребро из [math]v[/math]. По алгоритму вершина [math]v[/math] будет покрашена в черный цвет тогда, когда завершится обход всех вершин, достижимых из нее по одному ребру, кроме тех, что были рассмотрены раньше нее. Таким образом, вершина [math]v[/math] может стать черной только тогда, когда [math]dfs[/math] выйдет из вершины [math]u[/math], и она будет покрашена в черный цвет. Получаем противоречие.
[math]\triangleleft[/math]


Лемма о белых путях

Лемма:
Пусть дан граф [math]G[/math]. Запустим [math]dfs(G)[/math]. Остановим выполнение процедуры [math]dfs[/math] от какой-то вершины [math]u[/math] графа [math]G[/math] в тот момент, когда вершина [math]u[/math] была выкрашена в серый цвет (назовем его первым моментом времени). Заметим, что в данный момент в графе [math]G[/math] есть как белые, так и черные, и серые вершины. Продолжим выполнение процедуры [math]dfs(u)[/math] до того момента, когда вершина [math]u[/math] станет черной (второй момент времени).
Тогда вершины графа [math]G\setminus u[/math], бывшие черными и серыми в первый момент времени, не поменяют свой цвет ко второму моменту времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины [math]u[/math] по белым путям.
Доказательство:
[math]\triangleright[/math]

Черные вершины останутся черными, потому что цвет может меняться только по схеме белый [math]\to[/math] серый [math]\to[/math] черный. Серые останутся серыми, потому что они лежат в стеке рекурсии и там и останутся.
Далее докажем два факта:

Утверждение:
Если вершина была достижима по белому пути в первый момент времени, то она стала черной ко второму моменту времени.
[math]\triangleright[/math]
Если вершина [math]v[/math] была достижима по белому пути из [math]u[/math], но осталась белой, это значит, что во второй момент времени на пути из [math]u[/math] в [math]v[/math] встретится ребро из черной вершины в белую, чего не может быть по лемме, доказанной выше.
[math]\triangleleft[/math]
Утверждение:
Если вершина стала черной ко второму моменту времени, то она была достижима по белому пути в первый момент времени.
[math]\triangleright[/math]
Рассмотрим момент, когда вершина [math]v[/math] стала черной: в этот момент существует cерый путь из [math]u[/math] в [math]v[/math], а это значит, что в первый момент времени сущестовал белый путь из [math]u[/math] в [math]v[/math], что и требовалось доказать.
[math]\triangleleft[/math]
Отсюда следует, что если вершина была перекрашена из белой в черную, то она была достижима по белому пути, и что если вершина как была, так и осталась белой, она не была достижима по белому пути, что и требовалось доказать.
[math]\triangleleft[/math]