Поиск в графе 1
.pdf
Задача поиска в графе Поиск в ширину
Поиск в ширину и расстояние в графе
Теорема 1.3
Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.
Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T (ò. å. d(v0;v) = h(v)).
Ä î ê à ç à ò å ë ü ñ ò â î.
пусть s = h(v), очевидно путь длины s есть это путь по древесным ребрам наверх
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе Поиск в ширину
Поиск в ширину и расстояние в графе
Теорема 1.3
Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.
Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T (ò. å. d(v0;v) = h(v)).
Ä î ê à ç à ò å ë ü ñ ò â î.
пусть s = h(v), очевидно путь длины s есть это путь по древесным ребрам наверх покажем, что более короткого пути нет
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе Поиск в ширину
Поиск в ширину и расстояние в графе
Теорема 1.3
Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.
Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T (ò. å. d(v0;v) = h(v)).
Ä î ê à ç à ò å ë ü ñ ò â î.
пусть s = h(v), очевидно путь длины s есть это путь по древесным ребрам наверх покажем, что более короткого пути нет
из леммы 1.3 следует, что каждое ребро графа соединяет вершины, находящиеся либо на одном либо на соседних уровнях
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе Поиск в ширину
Поиск в ширину и расстояние в графе
Теорема 1.3
Пусть G связный граф, T дерево поиска в ширину, и вершина v0 является корнем поиска в ширину.
Тогда для любой вершины v графа расстояние между вершинами v0 è v в графе G равно уровню узла v в дереве T (ò. å. d(v0;v) = h(v)).
Ä î ê à ç à ò å ë ü ñ ò â î.
пусть s = h(v), очевидно путь длины s есть это путь по древесным ребрам наверх покажем, что более короткого пути нет
из леммы 1.3 следует, что каждое ребро графа соединяет вершины, находящиеся либо на одном либо на соседних уровнях
следовательно из вершины уровня s попасть в вершины уровня
0 не менее чем за s шагов |
# |
Расин О.В. |
Поиск в графе |