Глава 4. Ориентированные ациклические графы и деревья

Ориентированные ациклические графы

В этом разделе изучаются свойства важного класса ориентированных графов, а именно ациклических. Как мы знаем, ориентированный граф — ациклический, если он не содержит контуров. Очевидно, простейшим примером ациклического ориентированного графа является ориентированное дерево.

Основной результат, который мы получим в этом разделе, заключается в том, что вершины ациклического ориентированного графа G на n вершинах можно пометить таким образом целыми числами из множества {1, 2,..., n}, что если в графе G имеется дуга (i, j), то i < j.

Определенное нами упорядочение вершин называется топологической сортировкой. Топологически отсортированы, например, вершины ациклического ориентированного графа на рисунке 31.

Справедливость основного результата этого раздела определяется следующей теоремой:

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

Рисунок 31

Доказательство. Пусть Р: v1, v2..., vp — максимальный ориентированный путь графа G. Покажем, что полустепень захода v1 и полустепень исхода vp равны нулю.

Если полустепень захода не равна нулю, то существует такая вершина w, что в графе G имеется дуга (w, v₁). Возможны два случая.

Случай 1. Пусть . Тогда существует ориентированный путь Р: w, v₁, v₂,..., v_p, содержащий все дуги пути Р. Это противоречит максимальности упомянутого пути.

Случай 2. Пусть для некоторого i w=v_i. Тогда в графе G имеется контур С: v₁, v₂..., v_i, v₁. Это противоречит условиям теоремы.

Таким образом, не существует такой вершины w, что (w, v_i) — дуга графа С.

Другими словами, полустепень захода v₁ равна нулю. Рассуждая аналогичным образом, можно показать, что равна нулю полустепень исхода v_p. ▪

Для осуществления топологической сортировки вершин ациклического ориентированного графа G на n вершинах проделаем следующее.

Выберем произвольную вершину с нулевой полустепенью исхода. Это возможно, поскольку граф G — ациклический, а по теореме 1 в нем должна иметься хотя бы одна такая вершина. Пометим выбранную вершину целым n. Теперь удалим из графа G эту вершину и инцидентные ему дуги. Обозначим получившийся граф через G'.

Поскольку граф G' также ациклический, можно выбрать в нем вершину с нулевой полустепенью исхода. Пометим эту вершину целым числом n—1. Повторим описанную процедуру до тех пор, пока не пометим все вершины. Легко видеть, что эта процедура порождает топологическую сортировку вершин графа G.