<br>
''Следствие'' == Лемма о белых путях.==
{{Лемма
|statement =
Пусть дан граф <tex>G</tex>. Запустим <tex>dfs(G)</tex>. Остановим выполнение процедуры <tex>dfs</tex> от какой-то вершины <tex>u</tex> графа <tex>G</tex> в тот момент, когда вершина <tex>u</tex> была выкрашена в серый цвет (назовем его первым моментом времени). Заметим, что в данный момент в графе <tex>G</tex> есть как белые, так и черные, и серые вершины. Продолжим выполнение процедуры <tex>dfs(u)</tex> до того момента, когда вершина <tex>u</tex> станет черной (второй момент времени).
<br>Тогда вершины графа <tex>G\setminus u</tex>, бывшие черными и серыми в первый момент времени, не поменяют свой цвет ко второму моменту времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины <tex>u</tex> по белым путям.
|proof =
олололоЧерные вершины останутся черными, потому что цвет может меняться только по схеме белый <tex>\to</tex> серый <tex>\to</tex> черный. Серые останутся серыми, потому что они лежат в стеке рекурсии и там и останутся. <br>Далее докажем два факта:{{Утверждение|statement=Если вершина была достижима по белому пути в первый момент времени, то она стала черной ко второму моменту времени.|proof =Если вершина <tex>v</tex> была достижима по белому пути из <tex>u</tex>, но осталась белой, это значит, что во второй момент времени на пути из <tex>u</tex> в <tex>v</tex> встретится ребро из черной вершины в белую, чего не может быть по лемме, доказанной выше.}}{{Утверждение|statement=Если вершина стала черной ко второму моменту времени, то она была достижима по белому пути в первый момент времени.|proof =Рассмотрим момент, когда вершина <tex>v</tex> стала черной: в этот момент существует cерый путь из <tex>u</tex> в <tex>v</tex>, а это значит, что в первый момент времени сущестовал белый путь из <tex>u</tex> в <tex>v</tex>, что и требовалось доказать.}}Отсюда следует, что если вершина была перекрашена из белой в черную, то она была достижима по белому пути, и что если вершина как была, так и осталась белой, она не была достижима по белому пути, что и требовалось доказать.
}}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
