Поиск в графе 3
.pdf
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Основную идею обнаружению точек сочленения сначала рассмотрим на примере.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Основную идею обнаружению точек сочленения сначала рассмотрим на примере.
Рассмотрим граф, на котором был проиллюстрирован поиск в глубину и полученное дерево поиска (о указанными обратными ребрами)
Исходный граф |
|
||
v4 |
v1 |
v8 |
v9 |
v3 |
v2 |
v7 |
|
|
|
||
v5 |
|
v6 |
|
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Основную идею обнаружению точек сочленения сначала рассмотрим на примере.
Рассмотрим граф, на котором был проиллюстрирован поиск в глубину и полученное дерево поиска (о указанными обратными ребрами)
Исходный граф |
|
Дерево поиска в глубину |
|||||
v4 |
v1 |
v8 |
v9 |
||||
v1 |
|
|
|||||
|
|
|
|
|
|
||
|
v2 |
|
|
v2 |
v7 |
|
|
v3 |
v7 |
|
v3 |
v5 |
v8 |
||
|
|
|
|
|
v9 |
||
v5 |
|
v6 |
|
v4 |
v6 |
||
|
|
|
|
|
|||
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Основную идею обнаружению точек сочленения сначала рассмотрим на примере.
Рассмотрим граф, на котором был проиллюстрирован поиск в глубину и полученное дерево поиска (о указанными обратными ребрами)
Исходный граф |
|
Дерево поиска в глубину |
|||||
v4 |
v1 |
v8 |
v9 |
||||
v1 |
|
|
|||||
|
|
|
|
|
|
||
|
v2 |
|
|
v2 |
v7 |
|
|
v3 |
v7 |
|
v3 |
v5 |
v8 |
||
|
|
|
|
|
v9 |
||
v5 |
|
v6 |
|
v4 |
v6 |
||
|
|
|
|
|
|||
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Замечание 1
Если мы имеем изображение дерева поиска в глубину с указанными обратными ребрами, то по сути мы имеем изображение графа.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Замечание 1
Если мы имеем изображение дерева поиска в глубину с указанными обратными ребрами, то по сути мы имеем изображение графа.
Действительно, имея такое изображение, мы по сути имеем всю информацию о графе (а именно какие пары вершин являются смежными), а какие нет.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Замечание 1
Если мы имеем изображение дерева поиска в глубину с указанными обратными ребрами, то по сути мы имеем изображение графа.
Действительно, имея такое изображение, мы по сути имеем всю информацию о графе (а именно какие пары вершин являются смежными), а какие нет.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Замечание 1
Если мы имеем изображение дерева поиска в глубину с указанными обратными ребрами, то по сути мы имеем изображение графа.
Действительно, имея такое изображение, мы по сути имеем всю информацию о графе (а именно какие пары вершин являются смежными), а какие нет.
Рисунки на предыдущем слайде иллюстрируют это замечание.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Перед обсуждением примера необходимо сделать следующее
Замечание 1
Если мы имеем изображение дерева поиска в глубину с указанными обратными ребрами, то по сути мы имеем изображение графа.
Действительно, имея такое изображение, мы по сути имеем всю информацию о графе (а именно какие пары вершин являются смежными), а какие нет.
Рисунки на предыдущем слайде иллюстрируют это замечание.
В дальнейшем мы будем использовать этот прием (указывать только дерево поиска в глубину)
Расин О.В. |
Поиск в графе |
|
|