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

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

Функция L(v)

Для дерева поиска в глубину T графа G определим на множестве вершин графа функцию LT (v)

Åñëè V BT (v) = 0/,òî

LT (v) = num[v]

Åñëè V BT (v) = fu1;u2;:::;ukg,

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

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

Функция L(v)

Для дерева поиска в глубину T графа G определим на множестве вершин графа функцию LT (v)

Åñëè V BT (v) = 0/,òî

LT (v) = num[v]

Åñëè V BT (v) = fu1;u2;:::;ukg,òî

LT (v) = minfnum[v];num[u1];:::;num[uk]g

Если из контекста будет ясно, о какого дереве T идет речь, то будем писать просто L(v).

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

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

Функция L(v)

Для дерева поиска в глубину T графа G определим на множестве вершин графа функцию LT (v)

Åñëè V BT (v) = 0/,òî

LT (v) = num[v]

Åñëè V BT (v) = fu1;u2;:::;ukg,òî

LT (v) = minfnum[v];num[u1];:::;num[uk]g

Если из контекста будет ясно, о какого дереве T идет речь, то будем писать просто L(v).

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

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

Функция L(v)

Таким образом поскольку в дереве поиска в глубину чем выше вершина в дереве, тем меньшее ее номер,

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

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

Функция L(v)

Таким образом поскольку в дереве поиска в глубину чем выше вершина в дереве, тем меньшее ее номер, то если из поддерева Tv исходят обратные ребра в вершины, расположенные выше v,

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

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

Функция L(v)

Таким образом поскольку в дереве поиска в глубину чем выше вершина в дереве, тем меньшее ее номер, то если из поддерева Tv исходят обратные ребра в вершины, расположенные выше v, òî

LT (v) совпадает с порядковым номером самой высокой вершины достижимой по обратному ребру из вершин Tv

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

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

Функция L(v)

Таким образом поскольку в дереве поиска в глубину чем выше вершина в дереве, тем меньшее ее номер, то если из поддерева Tv исходят обратные ребра в вершины, расположенные выше v, òî

LT (v) совпадает с порядковым номером самой высокой вершины достижимой по обратному ребру из вершин Tv

если же таких обратные ребер нет (или их нет вообще), то LT (v) совпадает с порядковым номером самой вершины v

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

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

Ниже рассмотрен поясняющий пример

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

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

Ниже рассмотрен поясняющий пример

Дерево поиска в

глубину

v1

v2	v5	v7
v3		v8
		v6 v9
v4

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

	Поиск точек сочленения и блоков в графе				Модификация поиска в глубину для поиска точек сочлене
					Использование свойства точек сочленения в дереве поиск
	Ниже рассмотрен поясняющий пример
	Дерево поиска в
	глубину			Для вычисления значений L(v) достаточно
	v1		v7	сравнить между собой номера V B(v) è
	v2			num[v] и взять минимальный
	v3	v5	v8
			v6 v9
	v4

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