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

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

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

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

Лемма 1.3

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

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

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

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

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

Лемма 1.3

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

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

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

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

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

Лемма 1.3

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

находящиеся на одном уровне, либо вершины, уровни которых различаются на 1.

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

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

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

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

Лемма 1.3

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

находящиеся на одном уровне, либо вершины, уровни которых различаются на 1.

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

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

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

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

u

v'

v

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

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

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

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

u

v'

v

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

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

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

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

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

u

v'

v

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

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

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

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

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

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

u

v'

v

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

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

Åñëè h(v) > h(u) + 2,

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

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

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

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

u

v'

v

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

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

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

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

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

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

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

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

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