Редактирование: Лемма о белых путях

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
Не существует такого момента выполнения [[Обход в глубину, цвета вершин|поиска в глубину]], в который бы существовало ребро из черной вершины в белую.
 
Не существует такого момента выполнения [[Обход в глубину, цвета вершин|поиска в глубину]], в который бы существовало ребро из черной вершины в белую.
 
|proof =
 
|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>, и она будет покрашена в черный цвет. Получаем противоречие.
+
Пусть в процессе выполнения процедуры <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>
 
<br>
  
== Лемма о белых путях ==
+
''Следствие''
 +
== Лемма о белых путях.==
 
{{Лемма
 
{{Лемма
 
|statement =
 
|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> станет черной (второй момент времени).
+
Пусть дан граф <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> по белым путям.
+
Тогда вершины графа <tex>G\u</tex>, бывшие черными и серыми в нулевой момент времени, не поменяют свой цвет в первый момент времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины <tex>u</tex> по белым путям.
 
|proof =
 
|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>, что и требовалось доказать.
 
}}
 
Отсюда следует, что если вершина была перекрашена из белой в черную, то она была достижима по белому пути, и что если вершина как была, так и осталась белой, она не была достижима по белому пути, что и требовалось доказать.
 
}}
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: