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

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

Признак точки сочленения в дереве поиска в глубину

Лемма 1.2

Пусть T дерево поиска в глубину связного графа G. Вершина v является точкой сочленения графа G тогда и только тогда, когда выполняется одно из двух условий:

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

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

Признак точки сочленения в дереве поиска в глубину

Лемма 1.2

Пусть T дерево поиска в глубину связного графа G. Вершина v является точкой сочленения графа G тогда и только тогда, когда выполняется одно из двух условий:

1) v является корнем дерева T и имеет не менее двух сыновей;

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

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

Признак точки сочленения в дереве поиска в глубину

Лемма 1.2

Пусть T дерево поиска в глубину связного графа G. Вершина v является точкой сочленения графа G тогда и только тогда, когда выполняется одно из двух условий:

1) v является корнем дерева T и имеет не менее двух сыновей;

2) v не является корнем и для некоторого сына s вершины v íè одна вершин Ts не имеет обратного ребра, ведущего к собственному предку вершины v

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

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

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

1) Пусть у корня более одного сына s1, s2, . . . , sk (k > 1)

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

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

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

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

1) Пусть у корня более одного сына s1, s2, . . . , sk (k > 1)

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

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

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

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

1) Пусть у корня более одного сына s1, s2, . . . , sk (k > 1)

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

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

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

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

1) Пусть у корня более одного сына s1, s2, . . . , sk (k > 1)

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

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

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

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

1) Пусть у корня более одного сына s1, s2, . . . , sk (k > 1)

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

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

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

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

		Поиск точек сочленения и блоков в графе				Модификация поиска в глубину для поиска точек сочлене
						Использование свойства точек сочленения в дереве поиск
Доказательство леммы 1.2 1)
	1) Пусть у корня один сын s
	v			Все вершины графа кроме v содержатся
		s1		в поддереве Ts
		...
			...
	...

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

		Поиск точек сочленения и блоков в графе				Модификация поиска в глубину для поиска точек сочлене
						Использование свойства точек сочленения в дереве поиск
Доказательство леммы 1.2 1)
	1) Пусть у корня один сын s
	v			Все вершины графа кроме v содержатся
		s1		в поддереве Ts
				Поскольку древесные ребра часть ребер граф,
...
			...
	...

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