Поиск в графе 3
.pdf
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
|
|||||||||||||||
|
|
|||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|||||||
|
|
v7 |
|
становится несвязным) |
|
|||||||||||||
v2 |
v5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
v8 |
|
|
|||||||||||||||
|
|
v9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v4 |
|
v6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
|
|||||||||||||||
|
|
|||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|||||||
|
|
v7 |
|
становится несвязным) |
|
|||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
|
||||||||||||||
v3 |
v8 |
выполняется следующее условие: |
|
|||||||||||||||
|
|
v9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v4 |
|
v6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
|||||||||||||||||
|
|||||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|
|||||||
|
|
v7 |
|
становится несвязным) |
|||||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
||||||||||||||||
v3 |
v8 |
выполняется следующее условие: ó íåå åñòü |
|||||||||||||||||
|
|
v9 |
сын (вершина v5) |
||||||||||||||||
v4 |
|
v6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
|||||||||||||||||
|
|||||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|
|||||||
|
|
v7 |
|
становится несвязным) |
|||||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
||||||||||||||||
v3 |
v8 |
выполняется следующее условие: ó íåå åñòü |
|||||||||||||||||
|
|
|
сын (вершина v5) в поддереве, которого (Tv5 ) |
||||||||||||||||
v4 |
|
v6 |
v9 |
нет ни одной вершины, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
||||||||||||||||
|
||||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|
||||||
|
|
v7 |
|
становится несвязным) |
||||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
|||||||||||||||
v3 |
v8 |
|
выполняется следующее условие: ó íåå åñòü |
|||||||||||||||
|
|
|
сын (вершина v5) в поддереве, которого (Tv5 ) |
|||||||||||||||
v4 |
|
v6 v9 |
|
нет ни одной вершины, которая соединяется |
||||||||||||||
|
|
обратным ребром с собственным |
|
|
|
предком |
|
|
|
v2 |
||||||||
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
||||||||||||||||
|
||||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|
||||||
|
|
v7 |
|
становится несвязным) |
||||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
|||||||||||||||
v3 |
v8 |
|
выполняется следующее условие: ó íåå åñòü |
|||||||||||||||
|
|
|
сын (вершина v5) в поддереве, которого (Tv5 ) |
|||||||||||||||
v4 |
|
v6 v9 |
|
нет ни одной вершины, которая соединяется |
||||||||||||||
|
|
обратным ребром с собственным |
|
|
|
предком |
|
|
|
v2 |
||||||||
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Способ обнаружения точек сочленения в дереве поиска (на примере)
Продолжим обсуждение примера. Далее через Tvi будем обозначать
поддерево с корнем в вершине vi
(т. е. все вершины, которые являются потомками вершины vi è ñàìà vi )
Дерево поиска в |
|
Легко убедиться, что только v1 è v2 |
||||||||||||||||
|
||||||||||||||||||
глубину |
|
|
|
являются точками сочленения (только их |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
|
удаление приводит к тому, что граф |
|
|
|
|
|
|
|
|
||||||
|
|
v7 |
|
становится несвязным) |
||||||||||||||
v2 |
v5 |
|
Можно увидеть, что для вершины v2 |
|||||||||||||||
v3 |
v8 |
|
выполняется следующее условие: ó íåå åñòü |
|||||||||||||||
|
|
|
сын (вершина v5) в поддереве, которого (Tv5 ) |
|||||||||||||||
v4 |
|
v6 v9 |
|
нет ни одной вершины, которая соединяется |
||||||||||||||
|
|
обратным ребром с собственным |
|
|
|
предком |
|
|
|
v2 |
||||||||
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Расин О.В. |
Поиск в графе |
|
|