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

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

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