Построение нормализованного графа

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

что оказывается удобным при вычислениях:

.

В любом зависимой вершине переменная определяется алгебраической суммой составляющих от всех остальных вершин. Например, для вершины :

, (1)

где N – число вершин графа, - передачи входящих в вершину k рёбер (если в ней нет входящего ребра от какой-то вершины i, то соответствующая передача считается равной нулю). Так как в каждом узле переменная определяется формулой (1), то граф соответствует системе линейных уравнений

, где . (2)

Передачу рёбер можно записать в виде квадратной NxN матрицы . (Здесь i – номер строки, j – номер столбца, т.е. в строки записываются передачи к данному узлу от всех вершин, а в столбцы - от данного узла ко всем узлам). Если все элементы строки являются нулями, то соответствующая вершина является источником, если все элементы столбца являются нулями, то соответствующая вершина является стоком.

Пусть задана система линейных уравнений:

, (3)

по которой нужно построить граф.

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

Вершины, которым соответствуют переменные , являются зависимыми, независимым переменным соответствуют правые части. В однородных системах все узлы являются зависимыми.

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

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

Для построения нормализованного графа систему (3) переписывают таким образом, чтобы в каждом уравнении коэффициент при одной переменной был равен 1. Для этого переносят все члены уравнения, не содержащие эту переменную, в правую часть, и выражают нормализованную переменную через остальные. Например, первое уравнение системы примет вид:

.

Переписывая второе уравнение в виде, нормализованном относительно , третье - относительно , и т.д., получим соответствующие строки матрицы .

Матрица имеет вид:

,

где , , ; , , и т.д.

Или, в общем виде, ; ;

; .

После этого, в соответствии с матрицей , нужно соединить узлы графа между собой. Матрица полученного нормализованного графа называется нормализованной. В ней все элементы главной диагонали равны нулю, что соответствует отсутствию петель в нормализованном графе.

Пример 1. По данной системе уравнений построить нормализованный граф, не составляя матрицу А_н в явном виде, затем по графу составить матрицу А_н.

.

Для данной системы , следовательно, число вершин .

Запишем систему в следующем виде: . Нормализованный граф изображен на рис. 29.

Рис. 29.	Рис. 30.

Над вершинами графа указаны их номера, под вершинами – соответствующие зависимые или независимые переменные (в данном случае это числа 1 и 3, обведенные окружностью). Нормализованная матрица приведена на рис. 30.

.

Определим число вершин: (рис 31). Из первого уравнения (рис. 32).

Рис. 31.	Рис. 32.

Из второго уравнения (рис. 33), из третьего – (рис.34), из четвертого – (рис.35). Объединяя все части, получим граф, изображенный на рис. 36.

Рис. 33.	Рис. 34.
Рис. 35.	Рис. 36.

 

Нормализованная матрица .

Пример 2. По заданной системе уравнений

составить матрицу А_н , считая источником , затем построить нормализованный граф. По графу составить систему уравнений.

Нормализованная матрица и нормализованный граф имеют следующий вид:

Нормализованному графу соответствует следующая система уравнений:

.

§7. Задача о кратчайшем пути на графе.
Алгоритм Дейкстры

Напомним, что сетью называется пара N=(G,α), где G – орграф, а α – функция из множества вершин графа в множество действительных чисел. Другими словами, каждой дуге графа поставлено в соответствие некоторое неотрицательное число, которое в данном случае называется длиной дуги. Введем длину пути как сумму длин дуг, составляющих путь. Расстоянием d(u,v) от вершины uдо вершины v называется длина кратчайшего пути из u в v. Если нет ни одного пути из u в v, то считают d(u,v)=∞. Расстояние от u до u равно нулю.

Для сети N возникает задача нахождения расстояния d(u,v) для данных вершин u и v и соответствующего кратчайшего пути. Известно несколько способов решения этой задачи. Мы рассмотрим один из них, основой которого является алгоритм Дейкстры. Он вычисляет расстояние от фиксированной вершины v₀ до всех остальных вершин сети.

Прежде, чем привести описание алгоритма, введем необходимые обозначения. Пусть N=(G,α) – сеть, v₀ – фиксированная вершина этой сети, v₁,…,v_m – остальные вершины. На множестве пар вершин (u,v) введем функцию L(u,v) следующим образом:

L(u,v)=	α(e), если e – дуга с началом в u и концом в v,
∞ – если такой дуги не существует.

В описании алгоритма участвует еще некоторое подмножество S множества V вершин графа. В ходе выполнения алгоритма вершины последовательно исключают из S, до тех пор, пока не останется ни одной, и вычисляют величины d(v_i),равные кратчайшему пути из v₀вv_i ,не содержащему вершин из S. Алгоритм также имеет графическую реализацию, в которой множеству S соответствуют неокрашенные вершины, а окрашивание – это исключение вершины из S. Итак, дадим формальное описание алгоритма Дейкстры.

Шаг 1. (инициализация).ПоложитьS:=V\{v₀} (то есть окрасить вершину v₀), d(v_i)=∞для всех i=1,…,m, положить y= v₀.

Шаг 2. Для всех v S (т.е. для всех неокрашенных вершин) пересчитать d(v) по формуле: d(v) =min{ d(v), d(y)+L(y,v)}. Если все d(v)= ∞, перейти к шагу 5 (это означает, что в графе отсутствуют пути из v₀в неокрашенные вершины).

Шаг 3. Выбрать в S вершину w,для которой величина d(v) минимальна, и положить S:=S\{w}, т.е. окрасить вершину w.Окрасить дугу, ведущую в вершину w из вершины, которая была взята в качестве y последний раз, когда в менялось значение d для вершины w . Положить y= w. Если S не пусто, перейти к шагу 2, иначе к шагу 4.

Шаг 4. Конец работы алгоритма.

При графической реализации алгоритма для графа будет построено покрывающее дерево с корнем в вершине v₀ (если оно существует). Если требуется определить не сам кратчайший путь, а лишь его длину, то можно не проводить окрашивание, а только вычислять на каждой итерации множество S . Расчет условно оформлять в виде таблице, как показано в следующем примере.

Пример 1.Для графа, изображенного на рис. 37, найти расстояния от вершины v₀до остальных вершин и построить дерево кратчайших путей с корнем в v₀.

Рис. 37.

Работа алгоритма будет иллюстрироваться заполнением приведенной ниже таблицы. Кроме того, для каждой строки таблицы приводится рисунок, соответствующий графической реализации алгоритма; на этом рисунке окрашенные вершины изображаются черным кружком, окрашенные ребра выделены жирными линиями.

 

№	y	d(v1)	d(v2)	d(v3)	d(v4)	d(v5)	Рисунок
	v0	¥	¥	¥	¥	¥	Рис.38
	v0			¥	¥	¥	Рис.39
	v2			¥		¥	Рис.40
	v1						Рис.41
	v3						Рис.42
	v4						Рис.43

 

Строка с номером ноль соответствует состоянию переменных после выполнения шага 1. Клетка d(v_i)заполняется только для вершин, входящих в S. Пока это все вершины, кроме v₀. Строка номер 1 показывает состояние переменных после выполнения шага 2. Действительно, L(v₀, v₁)=4 (см. рис.37), следовательно, новое значение для d(v₁)есть min(4, ∞)=4. Аналогично вычисляются остальные значения d(v_i). Наименьшим из них является d(v₂)=1 (выделено жирным шрифтом), следовательно, на шаге 3 вершина v₂будет принята в качестве w, окрашена и исключена из S. Значение d(v₂)изменилось последний раз при переходе от строки 0 к строке 1, в строке 1 стоит y= v₀,значит, окрашиваем ребро, ведущее из v₀в v₂ (см. рис. 39). После этого присваиваем переменной yзначение v₂,и, таккак есть еще неокрашенные вершины, переходим опять к шагу 2. На этом первый проход алгоритма заканчивается. Заметим, что d(v₂)=1 является расстоянием от v₀до v₂.

 

Рис. 38.	Рис. 39.	Рис. 40.

 

При втором проходе на шаге 2 снова пересчитываются значения d(v_i)для неокрашенных вершин. (Заметим, что фактически значения d(v_i) нужно пересчитывать лишь для вершин, которые имеют входящее ребро из вершины y, так как для остальных неокрашенных вершин L(y,v_i)=∞ ). Результат приведен в строке 2 таблицы. Минимальным является d(v₁)=3,поэтому на шаге 3 вершина v₁ будет окрашена и исключена из S. Кроме того, будет окрашено ребро, соединяющее v₂ и v₁ (рис. 40). После этого переменная w получает значение v₁ и мы снова переходим ко второму шагу.

На третьем проходе алгоритма после пересчета d(v_i)окрашивается вершина v₃и ребро, ведущее в неё из вершины v₁ (рис. 41).

 

Рис. 41	Рис. 42	Рис.43

 

На четвертом проходе получаются значения, приведенные в строке 4. Минимальным является d(v₄)=5. Последний раз значение d(v₄) менялось при переходе от строки 1 к строке 2, в строке 2 было y=v₂ , следовательно, нужно окрасить ребро, соединяющее v₂ с v₄ (рис. 42). Аналогично, на пятом проходе окрашиваем ребро, соединяющее v₅ с v₁. На этом работа алгоритма заканчивается, получившееся дерево кратчайших путей показано на рис. 43, расстояния от до остальных вершин выделены в таблице жирным шрифтом.

Алгоритм Дейкстры может быть применен и для поиска кратчайшего пути в неориентированном графе, для этого нужно в определении функции L(u,v) учитывать все ребра.

Пример 2. Найти расстояния от вершины v₁до остальных вершин и построить дерево кратчайших путей для следующего графа:

Результаты работы алгоритма приведены в таблице, дерево кратчайших путей – на рис. 44.

 

N	y	d(v2)	d(v3)	d(v4)	d(v5)	d(v6)	d(v7)	d(v8)	d(v9)
	v1	¥	¥	¥	¥	¥	¥	¥	¥
	v1				¥	¥	¥	¥	¥
	v2					¥	¥	¥	¥
	v4							¥	¥
	v3							¥	¥
	v5								¥
	v6
	v7
	v8

Рис. 44.

 

§8. Сетевое планирование

Теория графов оказалась мощным инструментом решения задач сетевого планирования. Сетевое планирование применяют для организации и составления календарных планов реализации больших комплексов работ. Это, например, научно-исследовательские работы с участием нескольких институтов, разработка автоматизированной системы бухгалтерского учета, строительство большого объекта и т. д. Управление всеми этими работами можно осуществлять с помощью метода критического пути. Использование этого метода позволяет сравнительно просто выяснить, когда необходимо начинать и заканчивать выполнение отдельных операций, как задержка хода выполнения некоторой операции влияет на время завершения всего проекта.

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

Пример 1. В следующей таблице приведены данные для проекта, состоящего из шести операций. Для каждой из них задана продолжительность и указаны непосредственно предшествующие ей операции.

Таблица 1.

Операция	Предшествующие операции	Время выполнения
a1	–
a2	–
a3	–
a4	a1, a2
a5	a2, a3
a6	a4, a5

Взаимосвязь отдельных работ проекта удобно задавать с помощью ориентированного графа, называется сетевым графиком. Каждой операции соответствует дуга графа. Связи между операциями также представляются в виде дуги. Дугу-связь проводят из конца дуги, соответствующей предшествующей операции, в начало следующей операции. Чтобы отличить операции от связей, операции изображают сплошными линиями, а связи – пунктирами.

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

Пример 2. Сетевой график для проекта, заданного таблицей 1, изображен на рис. 45.

Рис. 45.

Большое количество дуг в сети усложняет решение задачи. Поэтому, прежде всего, нужно упростить полученную сеть. Для этого можно выбросить некоторые дуги-связи. Начало и конец выбрасываемой дуги объединяют в одну вершину. При этом нужно проверять, не нарушится ли порядок выполнения операций после выбрасывания дуги. Проверку проводят по таблице, задающей проект.

Пример 3. Упростить сетевой график некоторого проекта, изображенный на следующем рисунке.

При упрощении выброшены дуги α, β, γ. Последовательность выполнения работ при этом не изменилась. Дугу δ выбросить нельзя, так как после этого дуги – работы a₄ и a₇ будут неразличимы (рис. 46).

Рис. 46.

Сетевой график не может содержать циклов. Действительно, если предположить, что имеется некоторый цикл (a₁, a₂, …, a_n-1, a_n, a₁), то операция a₁ может быть выполнена только после завершения операции a_n , операция a_n только после завершения операции a_n-1, ..., операция a₂ – только после завершения операции a₁. В этом случае проект никогда не может быть выполнен.

Сеть может содержать несколько начальных вершин (таких вершин, в которые не входит ни одна дуга). В этом случае можно добавить еще одну вершину и провести из нее дуги во все начальные вершины. Тогда сеть будет иметь одну начальную вершину. Аналогично вводят конечную вершину (вершина, из которой не выходит ни одна дуга).

После построения сетевого графика нумеруют его вершины. Нумерацию, при которой номер начала любой дуги меньше номера ее конца, называют правильной. Алгоритм получения правильной нумерации вершин следующий:

1. Нумеруют все начальные вершины.

2. Вычеркивают все дуги, выходящие из начальных вершин. При этом получают новые начальные вершины. Если не все вершины перенумерованы, переходят к шагу 1.

Конечная вершина получает при этом наибольший номер.

Рассмотрим временные параметры сетевого графика. Предположим, что выполнение работы начато в момент времени t=0. Пусть t_ij – заданная продолжительность работы (v_i, v_j), которая соответствует ребру, соединяющему вершины v_i и v_j. Величины t_ij записывают на соответствующих дугах сетевого графика и считают их длинами.

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

Если из вершины v_i выходит несколько работ, то ранние сроки начал этих работ совпадают и называются ранним сроком наступления события v_i. Ранний срок начала работы (v_i, v_j) обозначают через , а ранний срок наступления события v_i – через . Для удобства величины записывают в верхней трети каждой вершины (рис. 47).

Рис. 47.

Если работа начата в ранний срок начала, то время ее окончания называется ранним сроком окончания работы. Ранний срок окончания работы (v_i, v_j) обозначается .

Будем считать, что нумерация вершин является правильной, и вместо v_iбудем указывать только номер i этой вершины.

Для вычисления ранних сроков наступления событий используют следующий алгоритм, называемый алгоритмом Форда.

1. Полагают .

2. Для i=2, 3, ..., п вычисляют , где B_i – множество вершин, из которых выходят ребра, входящие в вершину i.

Номер k той вершины, для которой получено значение , заносят в левую треть вершины i (рис. 47).

После нахождения величин рассчитывают ранние сроки начал и окончаний работ по формулам:

= , = + t_ij .

Пример 4. Найти ранние сроки начал и окончаний работ для сети, изображенной на рис. 48.

Рис. 48.

Полагаем . После этого рассматриваем вершины в
порядке их номеров: . В левую треть
вершины v₂ ставим номер вершины v₂; далее, . В левую треть вершины v₃ записываем номер вершины v₂ (так как при движении из v₂получено значение ). Аналогичным образом вычисляем, что и . После этого находим ранние сроки начал и окончаний работ: , , , , , , , , , , , . Результаты вычислений вносим на сетевой график (рис. 49).

Рис. 49.

Критическое время и критический путь. Ранний срок наступления конечного события называется критическим временем и обозначается . Весь проект не может быть завершен раньше момента времени , т. е. критическое время – это минимальный срок окончания всего комплекса работ. На сетевом графике – это длина пути наибольшей длины из начальной вершины в конечную.

Всякий путь длины равной из начальной вершины в конечную называется критическим путем. Для его построения используется следующий алгоритм. Начинают построение с конечной вершины. В ее левой трети стоит номер той вершины, при движении из которой определялся ранний срок наступления события. Критический путь идет из конечной вершины в вершину с этим номером; затем в вершину, номер которой стоит в левой трети полученной при движении вершины, и так до начальной вершины.

Пример 5.Для сети, изображенной на рис. 49, критический путь выделен жирной линией.

Если в какой-то вершине стоят два номера, то критический путь распадается на два. Таким образом, критических путей может быть несколько.

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

Поздние сроки начал и окончаний работ. Заметим, что каждое событие должно произойти не слишком поздно, чтобы обеспечить последовательное выполнение всех операций некоторого пути от этого события до конечного. С учетом этого всем событиям удобно сопоставить второе множество чисел, называемых поздними сроками наступления этих событий. Они аналогичны ранним срокам наступления, но их измерение производится относительно конечного события, а не начального. Дадим формальное определение. Зададим время Т выполнения всего комплекса работ. Очевидно, что должно выполняться неравенство Т≥ . Обычно берут Т= , что и предполагается в дальнейшем.

Поздним сроком окончания работы называется наибольшее допустимое время окончания работы без нарушения срока завершения всего проекта. Поздний срок окончания работы (v_i, v_j) обозначается . Можно определить поздний срок начала работы (v_i, v_j) по формуле

= – t_ij .

Поздним сроком наступления события v_j называется наиболее поздний срок окончания всех работ, входящих в соответствующую вершину. Для вычисления поздних сроков наступления событий используется следующий алгоритм.

1. Полагают .

2. Для j=n-1, n-2, ...,2, 1 вычисляют , где A_j – множество вершин, в которые входят ребра, выходящие из вершины j.

Таким образом, для конечной вершины поздний срок наступления событий совпадает со временем выполнения всего проекта. Затем просматривают все вершины в порядке убывания их номеров. Для каждой вершины рассматривают множество всех выходящих работ. Из поздних сроков наступления их концов вычитают продолжительность этих работ. Минимальная из этих разностей и равна . Величину записывают для удобства вычислений в правой трети вершины v_j (рис. 47).

Пример 6. Положим для сети, изображенной на рис. 48, время окончания всего комплекса работ Т= =15 и поставим это значение в правую треть вершины v₅. Перейдем к событию v₄: . Аналогично находим .

Из вершины v₂выходят две работы, поэтому

.

Аналогично получаем . Результаты вычислений приведены на рис. 50.

Рис. 50.

Из алгоритма вычисления поздних сроков следует, что увеличение позднего срока окончания проекта Т на t единиц ведет к увеличению поздних сроков наступления всех событий также на t единиц.

После определения можно вычислить поздние сроки начала и окончаний всех работ проекта:

= , = – t_ij .

Резервы времени. Рассмотрим некоторую работу (v_i, v_j). Найдем время, которое можно выделить для выполнения этой работы без задержки срока окончания всего проекта. Работа (v_i, v_j) не может быть начата раньше срока и должна быть закончена не позднее времени . Для выполнения этой работы можно затратить не более – единиц времени. По плану эту работу можно сделать за t_ij единиц времени.

Максимально допустимое время, на которое можно увеличить продолжительность выполнения работы (v_i, v_j)или отложить начало так, что это не вызовет задержки выполнения всего проекта, называется полным резервом времени.

Полный резерв времени работы (v_i, v_j)обозначают R_ij, он равен

R_ij= – – t_ij

Если полный резерв времени некоторой работы равен нулю, то задержка ее выполнения вызовет такую же по времени задержку выполнения всего проекта.

Если на некоторой работе использовать ее полный резерв, то путь, проходящий через эту работу, станет критическим. Полный резерв времени любой работы на этом пути станет равным нулю.

Найдем время, которое можно дополнительно выделить для выполнения работы (v_i, v_j) без введения дополнительных ограничений на время выполнения последующих работ. Для этого выполнение работы должно быть закончено к моменту времени . Таким образом можно выделить – единиц времени на выполнение работы (v_i, v_j).

 

Величина r_ij= – – t_ij называется свободным резервом времени работы (v_i, v_j). Если использовать свободный резерв на некоторой операции, то последующие работы могут быть по-прежнему начаты в свои ранние сроки.

Резервы времени удобно рассчитывать по сетевому графику, так как величины , записаны в его вершинах. Полученные значения резервов записывают около соответствующих дуг сетевого графика. Сначала ставят полный резерв, а затем свободный.

Отметим, что если поздние сроки найдены при Т= , то для любой работы (v_i, v_j), лежащей на критическом пути, = , = + t_ij, и следовательно, R_ij=r_ij=0.

Пример 7. Для сети, изображенной на рис. 50, имеем:

R₂₄= – – t₂₄=14–2–5=7, r₂₄= – – t₂₄=7–2–5=0,

R₄₅= – – t₄₅=15–7–1=7, r₄₅= – – t₄₅=15–7–1=7,

R₁₃= – – t₁₃=8–0–4=4, r₁₃= – – t₁₃=8–0–4=4.

Для остальных работ резервы времени равны н