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

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

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

Конечный неориентированный граф 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)

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

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

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

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

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

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

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

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	2	8	5	4	7	23	12	4	5	10	8

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

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

27