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

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

Чтобы использовать лемму 1.2 нам нужен какой-нибудь пригодный для ЭВМ способ описания свойства точек сочленения в дереве поиска

Далее мы перейдем к описанию такого способа

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

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

Чтобы использовать лемму 1.2 нам нужен какой-нибудь пригодный для ЭВМ способ описания свойства точек сочленения в дереве поиска

Далее мы перейдем к описанию такого способа

Через V BT (v) обозначим множество всех собственных предков w вершины v в дереве поиска T ,

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

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

Чтобы использовать лемму 1.2 нам нужен какой-нибудь пригодный для ЭВМ способ описания свойства точек сочленения в дереве поиска

Далее мы перейдем к описанию такого способа

Через V BT (v) обозначим множество всех собственных предков w вершины v в дереве поиска T , для которых существует обратное ребро uw из поддерева Tv.

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

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

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

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

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

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

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

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

глубину

v1

v2	v5	v7
v3		v8
		v6 v9
v4

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

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

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

	Поиск точек сочленения и блоков в графе						Модификация поиска в глубину для поиска точек сочлене
							Использование свойства точек сочленения в дереве поиск
	Ниже рассмотрен поясняющий пример
	Дерево поиска в					У корня нет собственных предков, поэтому
	глубину
						V B(v1)
	v1
			v7			Из поддерева Tv2 есть только одно
	v2	v5		v8		обратное ребро v4v1, поэтому
	v3
				v9
	v4		v6

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

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

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

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

глубину

v1

v2	v5	v7
v3		v8
		v6 v9
v4

У корня нет собственных предков, поэтому

V B(v1)

Из поддерева Tv2 есть только одно обратное ребро v4v1, поэтому

V B(v2) = fv1g

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

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

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

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

глубину

v1

v2	v5	v7
v3		v8
		v6 v9
v4

У корня нет собственных предков, поэтому

V B(v1)

Из поддерева Tv2 есть только одно обратное ребро v4v1, поэтому

V B(v2) = fv1g

Из поддерева Tv8 есть обратные ребра v8v1 è v9v7, поэтому

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

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

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

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

глубину

v1

v2	v5	v7
v3		v8
		v6 v9
v4

У корня нет собственных предков, поэтому

V B(v1)

Из поддерева Tv2 есть только одно обратное ребро v4v1, поэтому

V B(v2) = fv1g

Из поддерева Tv8 есть обратные ребра v8v1 è v9v7, поэтому

V B(v8) = fv1;v7g

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