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

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

Поиск в графе

Расин О.В.

14 апреля 2015 г.

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

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

Поиск точек сочленения в графе

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

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

Точки сочленения и мосты (общий случай)

Определение

Пусть G = (V;E) граф (возможно несвязный). Вершина v 2 V

называется точкой сочленения, если при ее удалении число компонент связности увеличивается.

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

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

Точки сочленения и мосты (общий случай)

Определение

Пусть G = (V;E) граф (возможно несвязный). Вершина v 2 V

называется точкой сочленения, если при ее удалении число компонент связности увеличивается.

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

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

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

Точки сочленения и мосты (общий случай)

Определение

Пусть G = (V;E) граф (возможно несвязный). Вершина v 2 V

называется точкой сочленения, если при ее удалении число компонент связности увеличивается.

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

Далее будем предполагать, что рассматриваемые графы (если не оговорено противное), являются связными

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск
	Примитивный алгоритм поиска точек сочленения
	Пусть G = (V;E) граф. Возьмем вершину v и удалим ее из
	графа.

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск
	Примитивный алгоритм поиска точек сочленения
	Пусть G = (V;E) граф. Возьмем вершину v и удалим ее из

графа.

С помощью любого из алгоритмов поиска проверяем является ли G v связным.

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск
	Примитивный алгоритм поиска точек сочленения
	Пусть G = (V;E) граф. Возьмем вершину v и удалим ее из

графа.

С помощью любого из алгоритмов поиска проверяем является ли G v связным.

Åñëè ãðàô G v несвязен, то v точка сочленения.

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

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск
	Примитивный алгоритм поиска точек сочленения
	Пусть G = (V;E) граф. Возьмем вершину v и удалим ее из

графа.

С помощью любого из алгоритмов поиска проверяем является ли G v связным.

Åñëè ãðàô G v несвязен, то v точка сочленения. В противном случае v не является точкой сочленения.

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

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

Пусть G = (V;E) граф. Возьмем вершину v и удалим ее из графа.

С помощью любого из алгоритмов поиска проверяем является ли G v связным.

Åñëè ãðàô G v несвязен, то v точка сочленения. В противном случае v не является точкой сочленения.

Выполнив эти действия для каждой вершины графа, мы найдем все точки сочленения графа.

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