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

	Поиск точек сочленения и блоков в графе				Модификация поиска в глубину для поиска точек сочлене
					Использование свойства точек сочленения в дереве поиск
	Ниже рассмотрен поясняющий пример
	Дерево поиска в
	глубину			Для вычисления значений L(v) достаточно
	v1		v7	сравнить между собой номера V B(v) è
	v2			Заметим, что в данном случае номер
				num[v] и взять минимальный
	v3	v5	v8	вершины совпадают с ее индексом
			v6 v9	num(vi) = i (в общем случае это не
	v4			обязательно так)

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

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

Модификация поиска в глубину для поиска точек сочлене

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

Ниже рассмотрен поясняющий пример

Дерево поиска в

глубину

Для вычисления значений L(v) достаточно

v1

v7

сравнить между собой номера V B(v) è

v2

Заметим, что в данном случае номер

num[v] и взять минимальный

v3

v5

v8

вершины совпадают с ее индексом

v6 v9

num(vi) = i (в общем случае это не

v4

обязательно так)

В следующей таблице приведены значения L(v) äëÿ âñåõ

вершин

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

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

Модификация поиска в глубину для поиска точек сочлене

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

Ниже рассмотрен поясняющий пример

Дерево поиска в

глубину

Для вычисления значений L(v) достаточно

v1

v7

сравнить между собой номера V B(v) è

v2

Заметим, что в данном случае номер

num[v] и взять минимальный

v3

v5

v8

вершины совпадают с ее индексом

v6 v9

num(vi) = i (в общем случае это не

v4

обязательно так)

В следующей таблице приведены значения L(v) äëÿ âñåõ

вершин

v

v1

v2

v3

v4

v5

v6

v7

v8

v9

V B(v)

0/

v1

v1

v1

v2

v2

v1

v1;v7

v7

L(v)

0/

1

1

1

2

2

1

1

7

Расин О.В.

Поиск в графе

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

Модификация поиска в глубину для поиска точек сочлене

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

Ниже рассмотрен поясняющий пример

Дерево поиска в

глубину

Для вычисления значений L(v) достаточно

v1

v7

сравнить между собой номера V B(v) è

v2

Заметим, что в данном случае номер

num[v] и взять минимальный

v3

v5

v8

вершины совпадают с ее индексом

v6 v9

num(vi) = i (в общем случае это не

v4

обязательно так)

В следующей таблице приведены значения L(v) äëÿ âñåõ

вершин

v

v1

v2

v3

v4

v5

v6

v7

v8

v9

V B(v)

0/

v1

v1

v1

v2

v2

v1

v1;v7

v7

L(v)

0/

1

1

1

2

2

1

1

7

Расин О.В.

Поиск в графе

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

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

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

Пусть T дерево поиска в глубину связного графа G.

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

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

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

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

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

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

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

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

2) v не является корнем и для некоторого сына s вершины

L(s) > num[v], ãäå

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

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

Используя функцию L(v) признак точки сочленения (лемму 1.2) можно переформулировать так

Лемма 1.4

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

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

2) v не является корнем и для некоторого сына s вершины

L(s) > num[v], ãäå

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

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