Эйлеровы графы и гамильтоновы циклы

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

Условия, при которых граф эйлеров.

Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны.

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

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

Эйлеровы цепи. Так называется цепь, включающая все ребра данного конечного неориентированного графа G, но имеющая различное начало (U’) и конец (U”).

Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность степеней всех вершин, кроме начальной и конечной. Последние две вершины должны иметь нечетные степени: из U’ мы лишний раз выходим, а в U” лишний раз входим. Эти условия достаточны для существования эйлеровой цепи.

Случай конечного ориентированного графа.

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

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

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

Гамильтоновым циклом называется простой цикл, проходящий через все вершины рассматриваемого графа. Такой цикл существует не во всяком графе (рис.2.9).

 

Да Нет

 

Рис.2.9 - Примеры графов

Несмотря на внешнюю схожесть, задачи распознавания эйлеровости и гамильтоновости графа принципиально различны. Правило определения эйлеровости приведено више. Что же касается гамильтоновости графа, то ответ на этот вопрос дает такая теорема, которая приводиться без доказательства: Граф со степенной последовательностью d1 £ d2 £... £ dn является гамильтоновым, если для всякого k, которое удовлетворяет неравенствам 1 £ k < n/2, истинна импликация (соответствие):

(dk £ k) Þ (dn-k ³ n - k) (2.8)

 

Существуют и другие, как более сильные, так і білее слабые теоремы и условия определения гамильтоновости графов.

Расчет сетевого графика

 

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

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

Рассмотрим использование положений теории графов при построении сети сложного комплекса работ или операций.

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

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

 

t _p - ранний срок наступления события;

t _n ­- поздний срок наступления события;

t _{i j­} - время операций;

i - номер предшествующего события;

j - номер последующего события;

R _п - полный резерв времени операции (i, j);

R - резерв времени события;

t _{p o} - ранний срок окончания операции (i, j);

t _{п о} - поздний срок окончания операции (i, j);

 

Основные временные параметры сетевого графика с детерминированным временем выполнения операций рассчитываются по следующим формулам:

1) ранний срок наступления события j

æ t ⁱ _p + t _{i j} , если к событию j подходит одна

t ^j _p = í операция (2.9)

è max {t ⁱ _p + t _{i j}}, если к событию j подходит

{i} несколько операций;

2) поздний срок наступления события j

æ t ^j _п - t _{i j} если от события j отходит одна

t ⁱ _п = í операция; (2.10)

è min {t ^j _п - t _{i j}}, если от события j отходит

{j} несколько операций

 

3) резерв времени события

 

R = t _n - t _p ; (2.11)

 

4) ранний срок окончания операции (i, j)

 

t _{p о} = t _p + t _{i j,} при t _{p o} = 0 (2.12)

 

5) поздний срок окончания операции (i, j)

 

t _{n о} = t _n (2.13)

 

6) полный резерв времени операции (i, j)

 

R _n = T_n - T_p - t _{i j} ; (2.14)

 

где R _n - максимальное время, на которое можно отсрочить или увеличить продолжительность работы (i, j), не изменяя директивного или раннего срока наступления завершающего события; R _п принимают минимальные значения для операций, лежащих на критическом пути; эти минимальные значения равны нулю, если директивный срок наступления завершающего события не задан или превышает начало выполнения операций на время, равное продолжительности критического пути.

Критический путь сетевого графика L_кр - это последовательность операций, продолжительность которых составляет минимальное время выполнения всего комплекса операций. Продолжительность критического пути называют критическим временем T_kp. Критический путь L_kp определяется как последовательностью операций с наименьшим полным резервом.

Расчет t _{p o} и t _p ведется от начала сетевого графика к концу, а расчет t _n и t _{n о} - от конца к началу. При этом для конечного события t _p = t _n .

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

Пример. В таблице записаны работы (i, j) и время их выполнения t_ij ;

 

i, j	1, 2	1, 3	2, 3	2, 5	3, 4	3, 6	4, 5	4, 6	4, 7	5, 7	6,7
tij

 

Начертить сетевой график и найти параметры сетевого графика по событиям и работам.

 

РЕШЕНИЕ По данным работам i, j строим сетевой график. Событий всего 7, значит рисуем 7 вершин. Надо так расположить вершины, чтобы работы i, j не пересекались.

 

27

2 4 5 2

2 1 29 10

3

2 12 39

7 0

0 15 39

1 0 5 4 2 5

0 17 8

7 8

8 8

3 0 23 31

8 6 0

t _p 31

N R

t _n

Рис. 2.10 - Сетевой график

Находим параметры по событиям.

1) Ранний срок наступления события i, t_p (i).Это максимальный путь от начального события до i - го события:

t_p(1) = 0; t_p(2) = t_1,2 = 2

В третье событие входят 2 работы: (2,3) и (1,3), значит

t_p(3)=max{t_p(2) + t_2,3 ; t_p(1) + t_1,3}=max{2+5, 8}= 8

В четвертое событие входит одна работа (3,4)

t_p(4) = t_p(3)+t_3,4 = 8+7=15

В пятое событие входят 2 работы: (2,5) и (4,5), значит

t_p(5)=max{t_p(2) + t_2,5 ; t_p() + t_4,5}=max{2+4, 15+12}= 27

В шестое событие входят две работы: (4,6) и (3,6), значит

t_p(6)=max{t_p(4) + t_2,5 ; t_p(3) + t_3,6}=max{15+4, 8+23}= 31

В седьмое событие входят три работы: (5,7); (4,7); (6,8) значит

t_p(7)=max{t_p(5) + t_5,7 ; t_p(4) + t_4,7; t_p(6) + t_6,7}=

max{5+5, 27+10,31+8}= 39

 

2) Поздний срок наступления события i, t_n (i) — это разность между продолжительностью максимального пути l_max и пути наибольшей продолжительности от данного события i до конечного события.

Рассчитывается t_n (i) по обратной схеме t_p (i). Значит, расчет начинаем от конечного события, ориентируемся на выходящие работы, берем минимум разности.

Для конечного события

t_n(7) = t_p(7)=39

Из шестого события выходит одна работа: (6,7)

t_n(6) = t_n­­­­­­­_­(7) - t_6,7 = 39 - 8 = 31

Из пятого события выходит одна работа: (5,7)

t_n(5) = t_n­­­­­­­­(7) - t_5,7 = 39 - 10 = 29

Из четвертого события выходит 3 работы: (4,5);(4,6);(4,7)

t_n(4) = min{ t_n­­­­­­­_­(5) - t_4,5 ; t_n­­­­­­­_­(6) - t_4,6 ; t_n­­­­­­­_­(7) - t_4,7 }=

min{29 - 12; 31 - 4; 39 - 5}= 17

Из третьего события выходит 2 работы: (3,4);(3,6)

t_n(3)=min{t_n­­­­­­­_­(4) - t_3,4 ; t_n­­­­­­­_­(6) - t_3,6}=min{17 - 7;31 - 23}= 8

Из второго события выходит 2 работы: (2,5);(2,3)

t_n(2)=min{t_n­­­­­­­_­(5) - t_2,5 ; t_n­­­­­­­_­(3) - t_1,3}=min{8 - 5;29 - 4}= 3

Из начального события выходит 2 работы: (1,2);(1,3)

t_n(1)=min{t_n­­­­­­­_­(2) - t_1,2 ; t_n­­­­­­­_­(3) - t_1,3}=min{3 - 2;8 - 8}= 0

Для начального события должно выполняться условие:

t_p(1) = t_n (1) = 0.

3) Находим резерв времени по событиям:

R(i) = t_n(i) - t_p(i).

R(1) = 0; R(2) = 3-2 =1; R(3) = 8-8 = 0;

R(4) = 17-15 = 2; R(5) = 29-27 = 2; R(6) = 31-31 = 0;

R(7) = 39-39 = 0.

 

4) Критический путь проходит по событиям с нулевым резервом времени R(i) = 0, т.е. 1, 3, 6, 7, (выделено на графе). Длина критического пути L_кр — это самый длинный путь от начального события до конечного:

L_кр = t_p(7) = 39.

Рассчитаем необходимые параметры по работам.

 

5) Ранний срок окончания работы (i, j):

t_p.o(i, j)=t_p(i) + t_i,j

t_p.o(1,2)=t_p(1) + t_1,2 = 0+2 = 2;

t_p.o(1,3)=t_p(1) + t_1,3 = 0+8 = 8;

t_p.o(2,3)=t_p(2) + t_2,3 = 2+5 = 7;

t_p.o(2,5)=t_p(2) + t_2,5 = 2+4 = 6;

t_p.o(3,4)=t_p(3) + t_3,4 = 8+7 = 15;

t_p.o(3,6)=t_p(3) + t_3,6 = 8+23 = 31;

t_p.o(4,5)=t_p(4) + t_4,5 = 15+12 = 27;

t_p.o(4,6)=t_p(4) + t_4,6 = 15+4 = 19;

t_p.o(4,7)=t_p(4) + t_4,7 = 15+5 = 20;

t_p.o(5,7)=t_p(5) + t_5,7 = 27+10 = 37;

t_p.o(6,7)=t_p(6) + t_6,7 = 31+8 = 39;

6) Поздний срок наступления окончания работы (i, j):

 

t_n.o (1,2) = t_n(2) = 3; t_n.o (2,3) = t_n(3) = 8;

t_n.o (1,3) = t_n(3) = 8; t_n.o (2,5) = t_n(5) = 29;

t_n.o (3,4) = t_n(4) = 17; t_n.o (4,5) = t_n(5) = 29;

t_n.o (3,6) = t_n(6) = 31; t_n.o (4,6) = t_n(6) = 31;

t_n.o (5,7) = t_n(7) = 39; t_n.o (4,7) = t_n(7) = 39.

t_n.o (6,7) = t_n(7) = 39;

 

7) Полный резерв времени работы i, j — это время, на которое можно увеличить продолжительность данной работы, не изменяя при этом продолжительность критического пути L_кр.

 

R_n(i, j) = t_n (j) - t_p(i) - - t_i,j;

R_n(1,2) = t_n (2) - t_p(1) - t_1,2 = 3-0-2 = 1;

R_n(1,3) = t_n (3) - t_p(1) - t_1,3 = 8-0-8 = 0;

R_n(2,3) = t_n (3) - t_p(2) - t_2,3 = 8-2-5 = 1;

R_n(2,5) = t_n (5) - t_p(2) - t_2,5 = 8-2-4 = 2;

R_n(3,4) = t_n (4) - t_p(3) - t_3,4 = 17-8-7 = 2;

R_n(3,6) = t_n (6) - t_p(3) - t_3,6 = 31-8-23 = 0;

R_n(4,5) = t_n (5) - t_p(4) - t_4,5 = 29-15-12 = 2;

R_n(4,6) = t_n (6) - t_p(4) - t_4,6 = 31-15-4 = 12;

R_n(5,7) = t_n (7) - t_p(5) - t_5,7 = 39-27-10 = 2;

R_n(6,7) = t_n (7) - t_p(6) - t_6,7 = 39-31-8 = 0;

 

Работа (4,7) имеет большой резерв времени (12), значит можно с этой работы снять на данном этапе ресурсы и перебросить их на работы лежащие на критическом пути. Аналогично, работы (2,5),(3,4),(4,5),(5,7) имеют резерв времени равный 2. Работу (2,3) считаем под критической, а работы с нулевым резервом времени — критические. На рисунке критический путь отмечен жирной линией.

 

2.8. Оптимизация на сетях.

Пусть S - произвольная, частично ориентированная сеть, каждому ребру u которой приписанное неотъемлемое число c(u) - пропускная способность. Потоком в сети S называется пара (f, w), где w - некоторая ориентация всех неориентированных ребер сети, а f(u) -заданная на множестве всех ребер функция с не отрицательными значениями, которые не превосходят пропускных способностей, и такая, что в каждой внутренней вершине a выполняется закон Кірхгофа, соответственно которой сумма значений потока по ребрам, которые входит в вершину, равно сумме потоков по ребрам, которые выходит с вершины. Иными словами, для f(u) выполняются условия:

0 £ f(u) £ c(u) для всех вершин сети;

R(a) = 0 для всех внутренних вершин, где

а G(a) (соответственно G'(a)) - множество всех ребер, которое выходят из a (соответственно входящих в a) при ориентации w.

Поскольку сумма значений R(a) по всем вершинах сети, включая полюса, равно нулю (каждое ребро есть исходным для одной вершины и входным для другой), то R(a_s) = - R(b_s). Значение R = R(a_s) называется величиной потока.

Рассмотрим задачу определения максимального значения Rmax потока через сеть S при заданных значениях пропускных способностей. Ответ может быть получен в терминах сечений сети.

Сечением сети называется множество ребер, при удалении которых сеть становится несвязной, причем полюса попадают в разные компоненты связности. В сети на рис.2.11 примерами сечений есть {d, e, f}, {b, c, e, g, h}, {d, g, h, i}.

 

7 a d h 2

a_S 2 c 4 e 3 g b_S

3 b 4 i

1

f

 

Рис. 2.11 - Задача максимального потока

 

Сечение называется простым, если при удалении какого-нибудь его ребра, оно перестает быть сечением. Да, сечения {d, e, f} и {b, c, e, g, h} есть простыми, а сечение {d, g, h, i} не является таким. По-видимому, что для каждого ребра простого сечения можно указать цепь, что проходить через это ребро, но не проходит через иные ребра данного сечения.

Если в связной сети выполняется простое сечение, то сеть распадается ровно на две части: левую часть, что содержит a_S, и правую часть, что содержит b_S. Каждое ребро простого сечения связывает вершины с разных частей. Будем называть ребро сечения прямым, если оно в сети не ориентированное или ориентирован слева по правой сторону, и обратным в противном случае. Будет ориентированное ребро прямым или обратным, зависит от выбора сечения. Так, в примере ребро е в сечениях {d, e, f} и {b, c, e, g, h} - обратное, а в сечении {a, c, e, g, i}- прямое.

Каждому простому сечению W припишем пропускную способность c(W), равную сумме пропускных способностей всех его прямых ребер. В примере на рис.2.11 сечение {d, e, f} имеет пропускную состоятельность 5+1=6, а сечение {b, c, e, g, h} - 3+2+3+2=10.

Теорема о максимальной пропускной состоятельность сети сформулированная Фордом и Фалкерсоном в таком виде: Максимальный размер потока Rmax через сеть S равно минимальной с пропускных способностей c_min ее простых сечений. Доказательство этой теоремы приведено в [2]. Эта теорема положена в основу задачи определения максимальной пропускной состоятельности сети.