Правильная нумерация вершин графа

ОПРЕДЕЛЕНИЕ 33. Нумерация вершин в ориентированном графе называется правильной (или топологической), если наличие дуги (v_i,v_j) означает, что i<j. В частности, любая нумерация вершин вполне несвязного графа является правильной.

Теорема 26. Для того, чтобы в ориентированном графе существовала правильная нумерация вершин, необходима и достаточна его ацикличность, т.е. в нем не должно быть циклов.

Доказательство. Пусть в ориентированном графе есть цикл. Докажем, что правильной нумерации вершин не существует. Пусть напротив правильная нумерация существует и цикл. Тогда – противоречие.

Пусть теперь граф ациклический. Существование правильной нумерации будем доказывать индукцией по числу вершин. Если вершина одна, то правильная нумерация очевидно существует (единственной вершине приписываем номер 1). Пусть утверждение справедливо для графа с p вершинами. Рассмотрим ациклический граф с (p +1) вершиной. Построим цепь с началом в произвольной вершине. Поскольку граф ациклический, то вершины в цепи не повторяются и поскольку число вершин графа конечное, то эта цепь не может продолжаться бесконечно. Вершина, для которой дальнейшее построение цепи невозможно, является стоком. Присвоим ей номер p +1. Удалив из графа эту вершину вместе с инцидентными дугами, получим ациклический граф с p вершинами, в котором по предположению вершины можно занумеровать правильно (числами от 1 до p). В результате получили правильную нумерацию вершин исходного графа.

Алгоритм построения правильной нумерации можно реализовать в виде таблицы. В первом столбце исходные номера вершин, во втором их непосредственные предшественники, в третьем новые номера (задающие правильную нумерацию). Находим вершину, у которой нет предшественников, присваиваем ей номер 1 (третий столбец) и ее старый номер вычеркиваем из второго столбца. Находим вершину, у которой оказалась пустой клетка во втором столбце, и присваиваем ей номер 2 и т.д. Если продолжение построения в какой-то момент невозможно, то в графе есть цикл.