Топологическая сортировка

Определение 5.17. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф*.

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

Определение 5.18. Уровень вершины сети — это натуральное число, определяемое следующим образом:

1. если полустепень захода вершины равна 0, то ее уровень равен 0 и наоборот (т.е. нулевой уровень N₀ — это множество всех входов);
3. если множества N_i вершин уровня i определены для всех i ≤ k, то уровень N_k+1 содержит те и только те вершины, предшественники которых принадлежат любому из уровней с номером от 0 до k, причем существует хотя бы один предшественник уровня k, т.е.
   N_k+1 = {v: Г^-1(v) ⊆ N₁ ∪...∪ N_k, Г^-1(v) ∩ N_k ≠ ∅},
   где Г^-1(v) = {х: х → v} — множество предшественников вершины v.

*В некоторых задачах встречаются бесконтурные ориентированные графы, имеющие бесконечные множества вершин и дуг. Такие графы называют бесконечными сетями. Мы рассматриваем только конечные сети. Кроме того, в литературе по теории графов термин „сеть" иногда используется в ином смысле — для объекта, более сложного, чем граф (см.: Яблонский СВ.).

Уровень вершины сети можно интерпретировать как длину максимального пути от входов сети до этой вершины.

Определение 5.19. Порядковой функцией сети G = (V, Е) называют отображение ord: V → N, сопоставляющее каждой вершине сети номер ее уровня.

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

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

Формально топологическую сортировку можно реализовать по-разному. Мы опишем один из возможных методов*.

Этот метод состоит в вычислении порядковой функции сети и известен как алгоритм Демукрона. Предполагается, что вершины сети пронумерованы от 1 до n.

* Другие методы топологической сортировки см.: Кнут Д.; Вирт Н.

Наглядно процесс определения уровней вершин можно представить следующим образом. Нулевой уровень образуют входы сети — вершины с полустепенью захода, равной 0. Удалив из сети все вершины нулевого уровня и исходящие из них дуги, вновь получим сеть, входами которой будут вершины первого уровня исходной сети. Указанный процесс „послойного" удаления вершин следует продолжать до тех пор, пока все вершины исходной сети не будут распределены по уровням.

Алгоритм Демукрона использует матрицу смежности вершин В типа n × n в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В. Можно увидеть, что сумма элементов k-го столбца матрицы В равна полустепени захода вершины v_k. Поэтому, просуммировав элементы матрицы по всем столбцам и выбрав вершины, соответствующие столбцам с нулевой суммой, получим множество вершин нулевого уровня — входы сети.

Безусловно, „физически" удалять вершины и дуги из сети и вычеркивать из матрицы В строки, соответствующие удаляемым вершинам, нет необходимости. Процесс вычисления порядковой функции можно организовать следующим образом. Запишем суммы элементов столбцов матрицы В в вектор М длины n. При этом элемент m_k вектора М будет содержать полустепень захода вершины v_k. Пусть из сети удалены вершина v_i и все исходящие из нее дуги. Заметим, что элемент b_ik равен 1, если из вершины v_i идет дуга в вершину v_k, и равен 0 в противном случае. Поэтому, чтобы получить новую полустепень захода вершины v_k, необходимо из элемента m_k вектора М вычесть элемент b_ik матрицы В. Чтобы пересчитать полустепени захода всех вершин сети, оставшихся в ней после удаления вершины v_i, надо из вектора М вычесть i-ю строку матрицы В.

Если на очередном шаге входами сети являются вершины v_i1 Для определения следующего „слоя" вершин нужно из вектора М вычесть строки матрицы В с номерами i₁,..., i_r и зафиксировать новые нулевые элементы вектора М, появившиеся после вычитания. Фиксировать следует именно новые нулевые элементы, поскольку элементы вектора М, соответствующие вершинам, лежащим на предыдущих уровнях, стали равными 0 на предыдущих шагах алгоритма.

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

Алгоритм Демукрона вычисления порядковой функции сети

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

0. Сформировать множество V₁ вершин сети. Значение счетчика уровней k положить равным 0. Найти суммы элементов по всем столбцам матрицы В (полустепени захода вершин) и заполнить ими массив М.

1. Если множество V₁ не пусто, перейти на шаг 2, если иначе, то перейти на шаг 3.

2. Определить множество I номеров всех новых нулевых элементов массива М, т.е. таких, что соответствующие этим номерам вершины принадлежат множеству V₁. Присвоить элементам массива Ord с номерами из множества I номер уровня k и удалить вершины с этими номерами из множества V₁ („замаскировать" вершины). Вычесть из массива М строки матрицы В, соответствующие вершинам с номерами из множества I (т.е. вершинам последнего вычисленного уровня). Увеличить счетчик уровней на 1 (k = k + 1). Вернуться на шаг 1.

3. Закончить работу.

Пример 5.15. Применим алгоритм Демукрона к сети, представленной на рис. 5.38. Матрица смежности вершин сети имеет следующий вид:

Приведем последовательность значений массива М, соответствующую итерациям алгоритма и множества N_i вершин i-го уровня. Прочерки соответствуют вершинам, не принадлежащим множеству V₁ („замаскированные" вершины) на соответствующем этапе алгоритма.

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

В заключение рассмотрим вопрос о связи понятий ориентированной сети и упорядоченного множества.

Так как сеть есть бесконтурный граф, то отношение достижимости в нем будет отношением порядка. Действительно, пусть для двух отличных друг от друга вершин u, v сети вершина и достижима из вершины v (v ⇒* u) и вершина v достижима из вершины u (u ⇒* v). Тогда существует путь ненулевой длины из v в u (v ⇒⁺ u) и из u в v (u ⇒⁺ v). Отсюда вытекает, что существует путь ненулевой длины из u в u (u ⇒⁺ u) и из v в v (v ⇒⁺ u). Следовательно, существует контур, связывающий вершины u и v, что невозможно.

Обратно, пусть (А, ≤) — конечное упорядоченное множество. Сопоставим ему ориентированный граф G = (V, Е) так, что множество вершин V находится с А во взаимно однозначном соответствии, а множество дуг определяется следующим образом: u → v тогда и только тогда, когда v доминирует над и в смысле порядка ≤.

Построенный таким образом ориентированный граф G будет сетью. Действительно, предположим, что в нем существует контур, содержащий некоторую вершину u. Тогда u ⇒ ⁺ u, так как контур есть путь ненулевой длины. Если u ⇒ ¹ u, то существует дуга (петля), ведущая из u в u, т.е. u → u. Но такой петли в графе G быть не может, так как ни один элемент не может доминировать над самим собой (отношение доминирования иррефлексивно).

Если же u ⇒ⁿ u, где n > 1, то существует вершина v, отличная от и, такая, что u ⇒⁺ v и v ⇒⁺ u, откуда, согласно построению графа G, следует, что u < v и v < u, но это невозможно. Итак, G — бесконтурный ориентированный граф, т.е. сеть.

Входы сети G есть минимальные элементы исходного упорядоченного множества, а выходы — максимальные. Кроме того, каждый уровень сети образует антицепь в упорядоченном множестве (А, ≤).

Построенная сеть G будет обладать еще одним интересным свойством: для любых трех попарно различных вершин u, v и w из того, что u → v и v → w, следует u ≁ w. Иначе говоря, в сети G отсутствуют все „замыкающие дуги", подобные дуге v₁ → v₃ для сети, изображенной на рис. 5.39. Такие сети будем называть простыми.

Итак, каждому упорядоченному множеству может быть сопоставлена простая сеть согласно описанной выше процедуре. Эта простая сеть может рассматриваться как вариант наглядного изображения конечного упорядоченного множества и использоваться как диаграмма Хассе. На рис. 5.40 показана сеть, сопоставленная множеству всех подмножеств трехэлементного множества {а, b, с}, упорядоченного отношением включения. Полезно сравнить эту сеть с диаграммой Хассе, приведенной на рис. 1.13.