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

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

Рис. 5.16. Ациклический ориентированный граф.

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

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

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

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

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

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

Случай 2. Пусть для некоторого Тогда в графе G имеется контур Это противоречит условиям теоремы.

Таким образом, не существует такой вершины w, что — дуга графа G. Другими словами, полустепень захода равна нулю.

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

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

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

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