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

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

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

2) Докажем обратное.

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

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

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

2) Докажем обратное. Пусть v не является корнем дерева T

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство леммы 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

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

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

Доказательство леммы 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 è пройти вверх до корня)

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

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

Доказательство леммы 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.

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