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

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

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

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

u

v'

v

Пусть uv поперечное ребро и num[u] < num[v]

По лемме 1.2 h[u] 6 h[v]

Если h(v) > h(u) + 2, тогда есть v0 = Father[v]

è h(v0) > h(u), но тогда по лемме 1.2 num[u] < num[v0]

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

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

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

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

u

v'

v

Пусть uv поперечное ребро и num[u] < num[v]

По лемме 1.2 h[u] 6 h[v]

Если h(v) > h(u) + 2, тогда есть v0 = Father[v]

è h(v0) > h(u), но тогда по лемме 1.2 num[u] < num[v0]

Таким образом вершина u была добавлена в очередь ранее v0, à значит и извлечена раньше

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

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

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

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

u

v'

v

Пусть uv поперечное ребро и num[u] < num[v]

По лемме 1.2 h[u] 6 h[v]

Если h(v) > h(u) + 2, тогда есть v0 = Father[v]

è h(v0) > h(u), но тогда по лемме 1.2 num[u] < num[v0]

Таким образом вершина u была добавлена в очередь ранее v0, à значит и извлечена раньше

в момент извлечения вершина v еще не посещалась (иначе она бы не стала сыном v0 )

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

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

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

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

u

v'

v

Пусть uv поперечное ребро и num[u] < num[v]

По лемме 1.2 h[u] 6 h[v]

Если h(v) > h(u) + 2, тогда есть v0 = Father[v]

è h(v0) > h(u), но тогда по лемме 1.2 num[u] < num[v0]

Таким образом вершина u была добавлена в очередь ранее v0, à значит и извлечена раньше

в момент извлечения вершина v еще не посещалась (иначе она бы не стала сыном v0 ) ,

поэтому v должна была обнаружена из u, и стать сыном u,

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

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

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

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

u

v'

v

Пусть uv поперечное ребро и num[u] < num[v]

По лемме 1.2 h[u] 6 h[v]

Если h(v) > h(u) + 2, тогда есть v0 = Father[v]

è h(v0) > h(u), но тогда по лемме 1.2 num[u] < num[v0]

Таким образом вершина u была добавлена в очередь ранее v0, à значит и извлечена раньше

в момент извлечения вершина v еще не посещалась (иначе она бы не стала сыном v0 ) ,

поэтому v должна была обнаружена из u, и стать сыном u,
противоречие	#

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

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

Поиск в ширину и расстояние в графе

Теорема 1.3

Пусть G связный граф,

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

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

Поиск в ширину и расстояние в графе

Теорема 1.3

Пусть G связный граф, T дерево поиска в ширину,

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

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

Поиск в ширину и расстояние в графе

Теорема 1.3

Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.

Тогда для любой вершины v графа

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

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

Поиск в ширину и расстояние в графе

Теорема 1.3

Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.

Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T

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

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

Поиск в ширину и расстояние в графе

Теорема 1.3

Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.

Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T (ò. å. d(v0;v) = h(v)).

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

пусть s = h(v), очевидно путь длины s есть

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