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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

1) v является корнем дерева T и имеет не менее двух сыновей;

2) v не является корнем и для некоторого сына s вершины

L(s) > num[v], ãäå

Действительно, если v не корень и точка сочленения, то

найдется сын s такой, что никакое обратное ребро из Ts íå ведет в вершину,

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

1) v является корнем дерева T и имеет не менее двух сыновей;

2) v не является корнем и для некоторого сына s вершины

L(s) > num[v], ãäå

Действительно, если v не корень и точка сочленения, то найдется сын s такой, что никакое обратное ребро из Ts íå ведет в вершину, расположенную выше v,

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

1) v является корнем дерева T и имеет не менее двух сыновей;

2) v не является корнем и для некоторого сына s вершины

L(s) > num[v], ãäå

Действительно, если v не корень и точка сочленения, то найдется сын s такой, что никакое обратное ребро из Ts íå ведет в вершину, расположенную выше v, что равносильно

num[v] 6 L(s)

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формула для вычисления функции L

Следующая лемма нужна для доказательства корректности алгоритма поиска точек сочленения

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формула для вычисления функции L

Следующая лемма нужна для доказательства корректности алгоритма поиска точек сочленения

Хотя ее формулировка громоздка, но по существу за ней скрывается простая идея (это следствие леммы 1.4)

Лемма 1.5

Пусть T дерево поиска в глубину связного графа G è v вершина дерева T .

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формула для вычисления функции L

Следующая лемма нужна для доказательства корректности алгоритма поиска точек сочленения

Хотя ее формулировка громоздка, но по существу за ней скрывается простая идея (это следствие леммы 1.4)

Лемма 1.5

Пусть T дерево поиска в глубину связного графа G è v вершина дерева T . Тогда

L[v] = min(num[v];num[u1];:::;num[uk];L[s1];:::;L[sp]);

(1)

ãäå vu1;:::;vuk множество всех обратных ребер, инцидентных v,

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формула для вычисления функции L

Следующая лемма нужна для доказательства корректности алгоритма поиска точек сочленения

Хотя ее формулировка громоздка, но по существу за ней скрывается простая идея (это следствие леммы 1.4)

Лемма 1.5

Пусть T дерево поиска в глубину связного графа G è v вершина дерева T . Тогда

L[v] = min(num[v];num[u1];:::;num[uk];L[s1];:::;L[sp]);

(1)

ãäå vu1;:::;vuk множество всех обратных ребер, инцидентных v, à

s1, s2;:::; sp все сыновья вершины v в дереве T:

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

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

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

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

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

Д о к а з а т е л ь с т в о. Обратные ребра в поддереве Tv можно разбить на два класса:

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

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

Д о к а з а т е л ь с т в о. Обратные ребра в поддереве Tv можно разбить на два класса:

1) обратные ребра, идущие из самой вершины (они очевидны учтены в (1) )

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