3. Топологические уровни графа алгоритма

Для упрощения изложения далее используется следующая терминология: топологическая сортировка графа алгоритма называется его параллельной формой, группа в топологической сортировке называется ярусом параллельной формы. Число ярусов в параллельной форме называется ее высотой, число вершин і-го яруса – шириной і-го яруса, а максимальное из этих чисел – шириной параллельной формы. Параллельная форма минимальной высоты называется максимальной, а ее высота – высотой алгоритма. Максимальная ширина параллельных форм называется шириной алгоритма.

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

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

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

Вопросы

1. Почему любая реализация алгоритма должна порождать определенную сортировку его операций?

2. Какими свойствами обладают группы операций, выделенные при сортировке вершин графа?

3. Почему вершины графа любого алгоритма можно разбить, по крайней мере, на три группы?

4. Какая разметка вершин графа называется топологической сортировкой?

5. Какими основными свойствами обладают топологические сортировки?

6. Что представляет из себя топологический уровень?

7. Какая топологическая сортировка называется обобщенной? Какими свойствами обладает обобщенная топологическая сортировка?

8. Какой граф называется линейно упорядоченным?

Литература

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

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

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

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

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

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