322
правки
Изменения
Нет описания правки
<br>
{{Лемма
|statement =
{{Утверждение
|statement=
Если вершина была достижима по белому пути в первый момент времени, то она стала черной ко второму моменту времени;.
|proof =
Если вершина <tex>v</tex> была достижима по белому пути из <tex>u</tex>, но осталась белой, это значит, что во второй момент времени на пути из <tex>u</tex> в <tex>v</tex> встретится ребро из черной вершины в белую, чего не может быть по лемме, доказанной выше.
Рассмотрим момент, когда вершина <tex>v</tex> стала черной: в этот момент существует cерый путь из <tex>u</tex> в <tex>v</tex>, а это значит, что в первый момент времени сущестовал белый путь из <tex>u</tex> в <tex>v</tex>, что и требовалось доказать.
}}
Отсюда следует, что если вершина стала была перекрашена из белой чернойв черную, то она была достижима по белому пути, и что если вершина как была, так и осталась белой, она не была достижима по белому пути, что и требовалось доказать.
}}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
