Теория графов

stify">     На  рисунке изображен сетевой график. Граф, не содержащий циклов и имеющий только один исток и только один сток, называется направленным графом. Сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф. При этом вершинами графа служат события сетевого графика, а дугами (ребрами) — работы сетевого графика.

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

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

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

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

 
Рисунок 3  –  Комплексные связи в сетевом графике 

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

     

      
Рисунок 4 – Введение фиктивной работы 

     Пусть, например, имеются три процесса A, B,C. При этом окончание процесса C зависит от результатов процессов A и B. В этом случае возникают двусторонние зависимости, которые можно изобразить так, как показано на рисунке 5.

     

      
Рисунок 5 – Двусторонние зависимости 

     Другое  правило построения сетевого графика  заключается в том, что если несколько  работ может начаться не после  полного, а после частичного выполнения определенной работы, то последнюю работу целесообразно представить как сумму ее частей, расчлененных событиями ( 1, 2, 3, 4и 5на рисунке 6).  

     

      
Рисунок 6 – Вариант представления последней работы

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

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

      
Рисунок 7 – Подставки в сетевом графике 

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

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

     Анализ  сетевой модели

     Параметры сетевой модели. Параметрами сетевой  модели являются:

1. наиболее ранее возможное время наступления j-го события, обозначаемое символом ;
2. самое позднее допустимое время наступления i-го события, обозначаемое символом ;
3. резерв времени данного события, обозначаемый символом ;
4. полный резерв времени работы (i,j), обозначаемый символом ;
5. свободный резерв времени работы (i,j), обозначаемый символом .

     Наиболее  раннее возможное время наступления  j-го события определяется следующий рекуррентной формулой:

     

       где — продолжительность (i,j)-й работы; — множество событий, предшествующих j-му событию.

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

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

     Полный  резерв времени работы (i, j) вычисляется по формуле

     

     Свободный резерв времени работы (i, j) вычисляется по формуле

     

1.3 Нахождение  максимального потока в сети

     Транспортной  сетью называется конечный Связный  орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ), называемое пропускной способностью дуги, и существует:

1. ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;
2. ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция  f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга  называется насыщенной потоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

      Разрезом  L  сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

     Теорема Форда-Фалкерсона.

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

     Пусть . Тогда выполняется равенство

                     (1)

     Если  , так как в противном случае, используя имеем , а следовательно, в силу существует путь нулевой длины из в , что противоречит условию . Но тогда из (1) получаем 

 

     Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального  потока в транспортной сети равна пропускной способности минимального разреза.

     Следствие 2. Пусть  - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений равна бесконечности, то - максимальный поток.

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

     Две основные процедуры (операции алгоритма):

     · операция расстановки пометок;

     · операция изменения потока.

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

1. не помечена;
2. помечена, но не просмотрена;
3. помечена и просмотрена.

     Расставлять пометки начнем с источника S. Он получит пометку Источник помечен, но не просмотрен. Остальные вершины не помечены. Чтобы источник S был помечен и просмотрен, надо поместить все вершины, смежные с  S.

     Вершина получит пометку , где .

     Теперь  все вершины  смежные с S, помечены, но не просмотрены. А вершина S помечена и просмотрена. Начнём просматривать ту из вершин , которая имеет наименьший индекс. Для этого нужно расставить пометки вершинам, смежным с . Если для вершины выполняется следующее условие , то она получит метку , где . Если же для вершины выполняется условие , то получает метку , где . Далее просматриваем следующую вершину, и так до тех пор, пока не пометим сток t или же пока нельзя будет больше пометить ни одной вершины, сток при этом останется не помеченным. Если сток окажется не помеченным, то процесс нахождения максимального потока в сети можно считать законченным, а если сток помечен, то нужно переходить к процедуре 2.

     Рассмотрим  процедуру изменения потока. Если вершина  имеет пометку , то заменяем на , если же вершина имеет пометку , то заменяем на

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

     Дана  сеть G(V,E) с источником S  и стоком t. Пропускные способности дуг указаны. Найти максимальный поток из S в t.

     Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

      •для  любой дуги величина , называемая потоком по дуге , удовлетворяет условию ;

      •для  любой промежуточной вершины  v выполняется равенство 

 

т.е. сумма  потоков по дугам, заходящим в  v, равна сумме потоков по дугам, исходящим из v.

     Для любого допустимого потока в транспортной сети D выполняется равенство: 

 

     По  определению допустимого потока имеем: 

                

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

     Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в , или, что то же самое – величина, равная сумме потоков по всем дугам, исходящим из

 

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