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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 9 промежуточных версий 2 участников)
Строка 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> станет черной (второй момент времени).
Тогда вершины графа <tex>G\u</tex>, бывшие черными и серыми в нулевой момент времени, не поменяют свой цвет в первый момент времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины <tex>u</tex> по белым путям.
+
<br>Тогда вершины графа <tex>G\setminus 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>, что и требовалось доказать.
 +
}}
 +
Отсюда следует, что если вершина была перекрашена из белой в черную, то она была достижима по белому пути, и что если вершина как была, так и осталась белой, она не была достижима по белому пути, что и требовалось доказать.
 +
}}
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

Версия 08:11, 3 февраля 2012

Лемма:
Не существует такого момента выполнения поиска в глубину, в который бы существовало ребро из черной вершины в белую.
Доказательство:
[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]