АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Волновые процессы и разметка графа

В.П. Пинчук

Анализ и построение алгоритмов. Краткий конспект лекций -

Запорожье: ЗНТУ, 2010.

Глава 6

Алгоритмы решения задач на графах

1. Волновые процессы и разметка графа

2. Связность

2. Задачи о кратчайших маршрутах

4. Изоморфность графов

5. Получение полных наборов графов

6. Поиск максимальной клики и вычисление плотности графа

5. Задача коммивояжера

Волновые процессы и разметка графа

Алгоритмы решения некоторых видов задач на графах могут быть построены на основе специальных процедур, которые мы будем называть волновыми процессами. В основе такой процедуры лежит некоторый пошаговый процесс разметки вершин графа, который позволяет

получить некоторую последовательность непересекающихся подмножеств вершин графа

V₀, V₁,..., V_m , где V_iÍV. При определенных условиях выделенные подмножества являются некоторым разбиением множества вершин. В литературе можно встретить такие понятия, как ярусное разложение графа и поиск в ширину, которые связаны с рассматриваемыми процедурами.

В данной главе мы рассмотрим базовую процедуру волнового процесса. В дальнейшем для решения некоторых конкретных задач, кроме базовой процедуры, будут использованы еще несколько ее модификаций.

Функции, определяемые графом

Рассмотрим граф g=(V,X). Рассмотрим две функции, определяемые орграфом.
Функция g(v) каждой вершине графа v ставит в соответствие подмножество вершин смежных к v, т.е. является отображением вида g: V ® 2^V. Таким образом, если vÎV, то g(v)Î2^V, а сама функция определяется следующим образом:

g(v) = {uÎV: <v, u>ÎX}. (1)

В работе [*] такая функция называется многозначным отображением вершины v в графе g.

Вторая из рассматриваемых функций - g(U) представляет собой отображение вида
g: 2^V ® 2^V, определим ее следующим образом:

. (2)

Таким образом, значение функции g(U) представляет собой подмножество только лишь тех вершин графа, в каждую из которых можно попасть, передвинувшись вдоль некоторого ребра из одной из вершин подмножества U.

Волновой процесс 1

Пусть имеем некоторый граф g=(V,X). Рассмотрим следующий процесс, позволяющий получить последовательность подмножеств вершин графа

V₀,V₁,...,V_s, (3)

где V_iÎV.

Предположим, что часть подмножеств V₀,V₁,...,V_s указанной выше последовательности уже получена. Тогда следующий элемент этой последовательности получим по следующему правилу:

. (4)

Если V_k+1 - пустое множество, последним элементом последовательности (3) считаем V_k.

Реализацию правила (4) можно представить в виде следующего алгоритма.

1. Припишем всем вершинам индекс ¥.

2. Выберем начальное подмножество V₀ÍV. Всем его вершинам присвоим индекс 0.

3. Пусть теперь подмножества V₀,V₁,..., V_s уже получены. Опишем процедуру получения V_k+1. В подмножество V_k+1 включаем конечные вершины всех ребер, у которых одна из вершин принадлежит множеству V_k, а вторая вершина имеет индекс, равный ¥. Если множество V_k+1 не пустое, всем его вершинам присваиваем индекс k+1, а само множество присоединяем к последовательности
V₀,V₁,..., V_k. Если V_k+1 - пустое множество, процесс завершен, а само множество в набор (3) не включается.

Описанную выше процедуру будем называть волновым процессом. Отметим следующие его свойства.

1. Используя волновой процесс для любого заданного подмножеста вершин V₀ÍV графа можно получить соответствующую ему последовательность подмножеств вершин V₀,V₁,..., V_s, V_iÍV.

2. Последовательность V₀,V₁,..., V_s будет разбиением множества вершин исходного графа в том и только в том случае, если он является связным.

3. Пусть имеем связный граф. Выполним волновой процесс, начиная с вершины a (т.е. считая, что V₀ = {a}). Припишем каждой вершине графа индекс, равный номеру подмножества – элемента полученного разбиения. Тогда расстояние от вершины a до любой другой вершины b будет равно индексу вершины b.

4. Пусть имеем произвольный (не обязательно связный) граф. Припишем каждой вершине начальный индекс, равный ¥. Выберем произвольно вершину графа a и будем считать, что V₀ = {a}.

Выполним волновой процесс с индексированием вершин (см. предыдущий п.). Если в графе не осталось ни одной вершины с индексом ¥, то граф является связным.

Дата добавления: 2015-09-27 | Просмотры: 558 | Нарушение авторских прав