Поиск в графе 1

Задача поиска в графе	Поиск в ширину

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

u не может быть корнем (т. к. иначе h[u] = 0),

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

u не может быть корнем (т. к. иначе h[u] = 0), следовательно, для u есть u0 такая, что u0 = Father[u],

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

u не может быть корнем (т. к. иначе h[u] = 0), следовательно, для u есть u0 такая, что u0 = Father[u],

аналогично есть w0 = Father[w]

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

u не может быть корнем (т. к. иначе h[u] = 0), следовательно, для u есть u0 такая, что u0 = Father[u],

аналогично есть w0 = Father[w]

очевидно, num[u0] < num[w0] (в противном случае w бы попала в Front ранее чем u, что влекло бы за собой num[w] < num[u],

т. е. противоречие)

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

u не может быть корнем (т. к. иначе h[u] = 0), следовательно, для u есть u0 такая, что u0 = Father[u],

аналогично есть w0 = Father[w]

очевидно, num[u0] < num[w0] (в противном случае w бы попала в Front ранее чем u, что влекло бы за собой num[w] < num[u],

т. е. противоречие)

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

u'	w'
u	w

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

По выбору w должно быть h[u0] 6 h[w0],

u'	w'
u	w

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

u'	w'
u	w

По выбору w должно быть h[u0] 6 h[w0], но тогда

h(u) = h(u0) + 1 6 h(v0) + 1 = h(v)

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Доказательство леммы

u'	w'
u	w

По выбору w должно быть h[u0] 6 h[w0], но тогда

h(u) = h(u0) + 1 6 h(v0) + 1 = h(v)

но это противоречит предположению h(u) > h(w)

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Свойство поперечных ребер

Напомним, что ребро, которое не принадлежит дереву поиска называется поперечным

Расин О.В.	Поиск в графе