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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
|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> по белым путям.
+
Тогда вершины графа <tex>G\setminus u</tex>, бывшие черными и серыми в нулевой момент времени, не поменяют свой цвет в первый момент времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины <tex>u</tex> по белым путям.
 
|proof =
 
|proof =
 
олололо
 
олололо
 
}}
 
}}

Версия 03:16, 28 ноября 2010

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