Изменения
Новая страница: «{{Лемма |statement = Не существует такого момента выполнения [[Обход в глубину, цвета вершин|поис…»
{{Лемма
|statement =
Не существует такого момента выполнения [[Обход в глубину, цвета вершин|поиска в глубину]], в который бы существовало ребро из черной вершины в белую.
|proof =
Пусть в процессе выполнения процедуры <tex>dfs</tex> нашлось ребро из черной вершины <tex>v</tex> в белую вершину <tex>u</tex>. Рассмотрим момент времени, когда мы запустили <tex>dfs(v)</tex>. В этот момент вершина <tex>v</tex> была перекрашена из белого в серый, а вершина <tex>u</tex> - белая. Далее в ходе выполнения алгоритма будет запущен <tex>dfs(u)</tex>, поскольку обход в глубину обязан посетить все белые вершины, в которые есть ребро из <tex>v</tex>. По алгоритму вершина <tex>v</tex> будет покрашена в черный цвет тогда, когда завершится обход всех вершин, достижимых из нее по одному ребру, кроме тех, что были рассмотрены раньше нее. Таких образом, вершина <tex>v</tex> может стать черной только тогда, когда <tex>dfs</tex> выйдет из вершины <tex>u</tex>, и она будет покрашена в черный цвет. Получаем противоречие.
}}
<br>
''Следствие''
== Лемма о белых путях.==
{{Лемма
|statement =
олололо
|proof =
олололо
}}
|statement =
Не существует такого момента выполнения [[Обход в глубину, цвета вершин|поиска в глубину]], в который бы существовало ребро из черной вершины в белую.
|proof =
Пусть в процессе выполнения процедуры <tex>dfs</tex> нашлось ребро из черной вершины <tex>v</tex> в белую вершину <tex>u</tex>. Рассмотрим момент времени, когда мы запустили <tex>dfs(v)</tex>. В этот момент вершина <tex>v</tex> была перекрашена из белого в серый, а вершина <tex>u</tex> - белая. Далее в ходе выполнения алгоритма будет запущен <tex>dfs(u)</tex>, поскольку обход в глубину обязан посетить все белые вершины, в которые есть ребро из <tex>v</tex>. По алгоритму вершина <tex>v</tex> будет покрашена в черный цвет тогда, когда завершится обход всех вершин, достижимых из нее по одному ребру, кроме тех, что были рассмотрены раньше нее. Таких образом, вершина <tex>v</tex> может стать черной только тогда, когда <tex>dfs</tex> выйдет из вершины <tex>u</tex>, и она будет покрашена в черный цвет. Получаем противоречие.
}}
<br>
''Следствие''
== Лемма о белых путях.==
{{Лемма
|statement =
олололо
|proof =
олололо
}}
