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

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

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

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

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

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

15. Сетевые графики

ОПРЕДЕЛЕНИЕ 34. Сетевым графиком называется ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком.

Сетевые графики широко используются при организации производства сложных работ. Вершинами являются состояния объекта, дугами – переходы из состояния в состояние, весами – сроки выполнения отдельных этапов работ. Особенно широко сетевые графики используются в строительстве. Естественным является вопрос о минимальных сроках производства. Для этого должны быть выполнены все виды работ. Поэтому минимальный срок равен максимальной длине (весу) пути из истока в сток. Этот путь называется критическим. В реальном производстве задержки работ, расположенных на критическом пути, приводят к срыву сроков производства. Если интерпретировать сетевой график как сеть дорог с односторонним движением, а веса как расстояния, то можно искать кратчайший путь от источника к стоку. Такую задачу мы уже рассматривали, в частности, был описан алгоритм Дейкстры. Для сетевого графика решение, возможно, проще. Кратчайший путь мы здесь также называем критическим.

Алгоритм построения критического пути начинается с правильной нумерации вершин графа (она возможна, поскольку граф ациклический). При этом исток приобретает номер 1, а сток – номер p. Пусть Г^1(i)= , т.е. это множество номеров вершин, непосредственно предшествующих i-й вершине.

Далее формируются пометки вершин s(i) следующим образом. s(1)=0,

Для i от 2 до p

Нц s(i)= (если ищется длиннейший путь),

s(i)= (если ищется кратчайший путь) Кц.

В результате получаем s(p) – вес критического пути. Для восстановления самого пути (или путей) можно сохранять номера предшественников, на которых достигается максимум (минимум) в цикле. Реализовывать этот алгоритм также целесообразно в виде таблицы.