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

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

Теорема 1.1

Алгоритм поиска точек сочленения вычисляет значения функции L(v) правильно для каждой вершины v

Доказательство приводиться не будет. В принципе оно является следствием из пояснений к алгоритму.

Теорема 1.2

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска точек сочленения требует O(n + m) операций.

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