12. Граф. Виды графа. Способы обозначения. Примеры.

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

ОCНОВНЫЕ виды графов: !!!

Граф, или неориентированный граф   — это упорядоченная пара  , где   — это не пустое множество вершин или узлов, а   — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

Смешанный граф   — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой  , где  ,   и   определены так же, как выше. [Рисунок]

- связным, если для любых вершин  ,  есть путь из   в  . [Рисунок]

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

- полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. [Рисунок]

- Граф, имеющий конечное множество вершин называют конечным.

- Граф, не имеющий ребер, называется пустым. [Рисунок]

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

- деревом, если он связный и не содержит нетривиальных циклов. [Рисунок]

13. Матрицы смежности и трансцендентности [скорее инцидентности !?].

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно наличию ребра из i-й вершины графа в j-ю вершину (1) или его отсутствию (0). .

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).

1. Неориентированный граф

   1. 1 – вершина инцидентна ребру

   2. 0 – вершина не инцидентна ребру

2. Ориентированный граф

   1. 1 – вершина инцидентна ребру, и является его началом

   2. 0 – вершина не инцидентна ребру

   3. -1 – вершина инцидентна ребру, и является его концом

Построим матрицу инцидентности сначала для неориентированного графа, а затем для орграфа.

 

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

14. Расчёт сетевого графика. (!)

Обозначим:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 t i p + t i j , если к событию j подходит одна

t j p =  операция

 max {t i p + t i j}, если к событию j подходит

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

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

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

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

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

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

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, tn ( i ) — это разность между продолжительностью максимального пути lmax и пути наибольшей продолжительности от данного события i до конечного события.

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

 t j п - t i j если от события j отходит одна

t i п =  операция ;

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

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

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

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

t_n(7) = t_p(7)=39

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

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

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

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

t_n(2)=min{t_n­­­­­­­_­(5) - t_2,5 ; t_n­­­­­­­_­(3) - t_1,3}=min{8 - 5;29 - 4}= 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.

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

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

L_кр = t_p(7) = 39.

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

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

ранний срок окончания операции ( 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 о} (i, j)= t _n (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кр.

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

R n = Tn  Tp  t i j ;

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

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) считаем под критической, а работы с нулевым резервом времени — критические. На рисунке критический путь отмечен жирной линией.