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

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

Пояснения к алгоритму

3. Íà øàãå 3, когда мы берем очередную вершину u из списка смежности v, åñëè u не посещалась

добавлена проверка, является ли v корнем (если да, то увеличиваем счетчик числа сыновей );

кроме того необходимо инициализировать значение L[u] номером вершины u

4. Íà øàãå 3, когда мы берем очередную вершину u из списка смежности v, åñëè u уже посещалась

проверяем является ли uv обратным ребром (не является ли u предком v) и что обратное ребро мы нашли "снизу" (условие num[v] > num[u]),

если да обновляем значение L[v]

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

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

Пояснения к алгоритму

3. Íà øàãå 3, когда мы берем очередную вершину u из списка смежности v, åñëè u не посещалась

добавлена проверка, является ли v корнем (если да, то увеличиваем счетчик числа сыновей );

кроме того необходимо инициализировать значение L[u] номером вершины u

4. Íà øàãå 3, когда мы берем очередную вершину u из списка смежности v, åñëè u уже посещалась

проверяем является ли uv обратным ребром (не является ли u предком v) и что обратное ребро мы нашли "снизу" (условие num[v] > num[u]),

если да обновляем значение L[v]

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится.

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится. Поэтому значение L[v] уже не измениться.

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится. Поэтому значение L[v] уже не измениться.

Сообщаем отцу вершины v значение функции L åå ñûíà.

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится. Поэтому значение L[v] уже не измениться.

Сообщаем отцу вершины v значение функции L ее сына. Проверяем выполняется ли признак точки сочленения

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится. Поэтому значение L[v] уже не измениться.

Сообщаем отцу вершины v значение функции L ее сына. Проверяем выполняется ли признак точки сочленения

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

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

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

Пояснения к алгоритму

5. Íà øàãå 3, все соседи вершины v просмотрены. В этом случае поддерево вершины v уже не изменится. Поэтому значение L[v] уже не измениться.

Сообщаем отцу вершины v значение функции L ее сына. Проверяем выполняется ли признак точки сочленения

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

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

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

Теорема 1.1

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

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

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

Теорема 1.1

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

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

Теорема 1.2

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

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