Построение топологической сортировки графа по топологическим сортировкам подграфов его разбиения

Как правило, чем сложнее устроен граф, чем больше его размерность, тем труднее построить его топологическую сортировку, тем больше времени занимает процесс его предобработки.

Предлагается алгоритм построения топологической сортировки графа алгоритма по сортировкам подграфов его разбиения; приводятся результаты вычислительного эксперимента, дающие возможность сравнить предлагаемый алгоритм с используемым ранее непосредственным построением топологической сортировки графа большой размерности [Воев].

Пусть граф является сложным для исследования и обработки в силу своей размерности или других причин, некоторые из которых уже указаны. Разложим граф на подграфы. Построим разбиение множества вершин : Ø, для .Каждое подмножество , определяет порожденный подграф графа . Для любого множества порожденным подграфом называется максимальный подгаф графа , множеством вершин которого является . Построение сортировки графа проведем на основе сортировок подграфов . Заметим, что , поскольку при выделении подграфов , происходит потеря ребер, инцидентных вершинам из разных подмножеств . Вследствие такой потери разрываются связи между вершинами графа , проход по которым может определить топологический индекс вершины. Отметим, что связный граф невозможно разбить на непересекающиеся подграфы, объединение которых давало бы исходный. Например, (рис.1), т.к. объединение не содержит ребро , а значит при построении топологической сортировки графа по топологическим сортировкам , не учитывается возможность получения вершинами исходного графа с индексами 5 и 6 топологических номеров по цепочке 1, 5, 6.

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

Определение 1. Множество

называется

множеством теряемых ребер графа при разбиении множества .

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

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

 

 

но пересечение этих подграфов не обязательно равно Ø. Например, для графа ,(см. рис.10.3) можно построить систему подграфов . Построим сортировки наименьшей длины для каждого подграфа в отдельности, при этом каким-либо образом пометив граничные вершины. Без ограничения общности рассуждений, принимается, что запись каждого топологического уровня сортировки содержит сначала индексы всех вершин, не являющихся граничными, а если присутствуют граничные вершины, их индексы завершают запись. Такие топологические сортировки будут иметь минимальное количество уровней, равное длине критического пути подграфа плюс единица (следствие 2 утверждения 123).

При построении сортировки произвольного графа для простоты изложения предположим, что количество определенных выше порожденных подграфов равно двум: , , а — их топологические сортировки, представляющие массивы, в которых последовательно выписаны топологические уровни, начиная с первого. Обозначим , — топологические номера вершины в , соответственно, — топологический номер граничной вершины в результирующей сортировке графа , , — корректировочные разности для . Корректировочной разностью подграфа , назовем разность между топологическим индексом вершины в сортировке и ее индексом в сортировке .

Предлагаемый алгоритм содержит следующие основные этапы:

— инициализуются значения корректировочных разностей для подграфов , и определяется порядок просмотра топологических сортировок: ; ; ;

— последовательный просмотр топологической сортировки .

Пусть — индекс очередной вершины в сортировке .

Если индекс соответствует неграничной вершине,

то

= + , возврат в начало этапа;

иначе —

переход на следующий этап;

— последовательный просмотр топологической сортировки .

Пусть — индекс очередной вершины в сортировке .

Если индекс соответствует неграничной вершине,

то

= + , возврат в начало этапа;

иначе —

М: если ,

то

;обновление корректировочных разностей:

; ; переход на предыдущий

этап;

если ,

то

если в пределах рассматриваемого топологического уровня

существует такая граничная вершина с индексом

, что ,

то

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

граничных вершин данного топологического уровня;

переход на метку М;

иначе —

()- ,

; ; переход на

предыдущий этап.

 

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

В вычислительном эксперименте исследовалась эффективность с точки зрения временных затрат предложенного алгоритма построения топологической сортировки графа по топологическим сортировкам его подграфов по сравнению с непосредственным построением сортировки графа. Эксперимент проводился на графах различных по структуре последовательных алгоритмов. При этом изменялась размерность и количество подграфов, на которые разбивался граф. При проведении эксперимента фиксировалась размерность графа, начиная с которой новый алгоритм работал быстрее. Представлены примеры некоторых графов небольшой размерности (рис.10.4).

Из полученных результатов вычислительного эксперимента, проведенного в среде MATLAB (табл.10.1), очевидно, что даже при сравнительно небольшом количестве вершин графа построение его топологической сортировки по топологическим сортировкам его подграфов происходит быстрее, чем непосредственное построение топологической сортировки всего графа. Это количество вершин фиксировалось, как только преимущество во времени достигало порядка с. С увеличением размерности графа преимущество возрастает. Например, для графа 1, количество вершин которого равно 250, а количество подграфов равно двум, время построения сортировки по предложенному алгоритму уже на 5 с меньше, чем при использовании алгоритма непосредственного построения топологической сортировки всего графа в целом. Кроме того, как следует из результатов эксперимента, чем больше количество подграфов разбиения графа, тем при большей его размерности достигается преимущество во времени по сравнению с построением топологической сортировки целого графа, как и предполагалось ранее.

 

Рис.10.4. Примеры используемых графов

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

Таблица 10.1 -

Результаты вычислительного эксперимента

Граф	Кол-во подграфов	Кол-во вершин в подграфах	Количество вершин графа, начиная с которого достигается преимущество предложенного алгоритма по времени
		96 / 105
		97 / 92 / 101
		122 / 76 / 62 / 60
		256 / 257
		161 / 161 / 161 / 160
		176 / 175
		139 / 138 / 139 / 138
		105 / 296
		150 / 173 / 177
		288 / 289
		217 / 218 / 216
		177 / 177 / 178 / 178
		98 / 139
		102 / 128 / 96 / 133

 

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

 

Вопросы

1. Когда возникает семейство «похожих» алгоритмов?

2. Всегда ли можно точно построить граф алгоритма, содержащего условные операции? Почему?

3. Можно ли по имеющейся топологической сортировке графа получить топологические сортировки его подграфов? Как это сделать? Когда возникает такая необходимость? Привести пример.

4. Что назыв ется множеством теряемых ребер графа, когда это множество возникает? Привести примеры.

5. Какие вершины графа называются граничными вершинами? Привести примеры.

6. Написать программу, реализующую алгоритм построения топологической сортировки объединения двух графов по имеющимся топологическим сортировкам этих графов.

 

Литература

1. Воеводин В.В. Параллельные вычисления / В.В.Воеводин, Вл.В.Воеводин. — СПб.: БХВ-Петербург, 2002. — 608 с.

2. Харари Ф. Теория графов / Ф.Харари; пер.с англ. В.П.Козырева. — М.: Мир, 1973. — 300 с.

3. Уилсон Р. Введение в теорию графов / Р.Уилсон. — М.: Мир, 1977. — 207 с.

4. Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофидес. — М.: Мир, 1978. — 432 с.

5. Новиков Ф.А. Дискретная математика для программистов / Ф.А.Новиков. — СПб.: Питер, 2006. — 364 с.

6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н.Иванов. — М.: Лаборатория Базовых Знаний, 2001. — 288с.

7. Кобозева А.А., Нариманова Е.В. Метод построения топологической сортировки объединения графов, используемый при распараллеливании последовательных алгоритмов / Труды Одесского политехнического университета. – 2006. - №2(26). - С. 156-161.

 

Лекция 11. Использование операций гомоморфизма при построении топологических сортировок графов

План