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

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

Доказательство леммы 1.2 2)

2) Докажем обратное. Пусть v не является корнем дерева T и для любого сына si åñòü обратное ребро из вершины xi поддерева Tsi ведущее в собственного предка wi вершины v Обозначим корень дерева через r

	r
	...
	wi
	...
	svi
xi	...
...

На рис. не исключены случаи xi = si èëè wi = r, однако wi 6= v

Легко видеть, что если мы удалим v, то для любой

вершины Tsi есть маршрут в корень r (достаточно перейти в xi, затем по ребру xiwi è пройти вверх до корня)

Аналогичным способом мы можем попасть из любого потомка v в корень r.

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

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

Доказательство леммы 1.2 2)

Очевидно, если вершина не является потомком v,

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

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

Доказательство леммы 1.2 2)

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

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

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

Доказательство леммы 1.2 2)

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

таким образом

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

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

Доказательство леммы 1.2 2)

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

таким образом

Для любой вершины u 6= v есть путь в графе, соединяющий u ñ корнем, и не проходящий через v

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

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

Доказательство леммы 1.2 2)

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

таким образом

Для любой вершины u 6= v есть путь в графе, соединяющий u ñ корнем, и не проходящий через v

таким образом после удаления v между любой парой оставшихся вершин остается маршрут

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

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

Доказательство леммы 1.2 2)

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

таким образом

Для любой вершины u 6= v есть путь в графе, соединяющий u ñ корнем, и не проходящий через v

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

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

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

Доказательство леммы 1.2 2)

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

таким образом

Для любой вершины u 6= v есть путь в графе, соединяющий u ñ корнем, и не проходящий через v

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

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

#

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

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

Использование свойства точек сочленения в дереве поиска в алгоритме

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

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

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

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