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

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

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

1) Пусть у корня один сын s

	v
		s1
...
			...
	...

Все вершины графа кроме v содержатся в поддереве Ts

Поскольку древесные ребра часть ребер граф, то после удаления v все они остаются в графе

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

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

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

1) Пусть у корня один сын s

	v
		s1
...
			...
	...

Все вершины графа кроме v содержатся в поддереве Ts

Поскольку древесные ребра часть ребер граф, то после удаления v все они остаются в графе

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

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

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

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

1) Пусть у корня один сын s

	v
		s1
...
			...
	...

Все вершины графа кроме v содержатся в поддереве Ts

Поскольку древесные ребра часть ребер граф, то после удаления v все они остаются в графе

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

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

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

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

1) Пусть у корня один сын s

	v
		s1
...
			...
	...

Все вершины графа кроме v содержатся в поддереве Ts

Поскольку древесные ребра часть ребер граф, то после удаления v все они остаются в графе

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

и, значит, получаем связный граф

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

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

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

1) Пусть у корня один сын s

	v
		s1
...
			...
	...

Все вершины графа кроме v содержатся в поддереве Ts

Поскольку древесные ребра часть ребер граф, то после удаления v все они остаются в графе

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

и, значит, получаем связный граф

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

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

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

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

2) Пусть v не является корнем.

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

r

v...	...
...

	s
	...
...	...

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

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

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

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

2) Пусть v не является корнем.

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

r

v...	...
...

	s
	...
...	...

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

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

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

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

2) Пусть v не является корнем.

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

r

v...	...
...

	s
	...
...	...

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

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

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

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

2) Пусть v не является корнем.

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

r

v...	...
...

	s
	...
...	...

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

Следовательно после удаления v

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

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

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

2) Пусть v не является корнем.

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

r

v...	...
...

	s
	...
...	...

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

Следовательно после удаления v вершины поддерева Ts1 "отделятся" от остальной части графа.

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

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