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