Контрольная работа по "Дискретная математика"

Задача1

В графе с помощью алгоритма Прима найти стягивающее дерево минимального веса.

Решение

Выберем вершину , которая будет корнем дерева. Из двух ребер, которые инцидентны вершине , выберем то, что имеет наименьший вес. Присоединим ребро 1 – 2 с весом 1 к вершине v1. К вершине v2 присоединим ребро с весом 1, - соединяющее вершины v2 и v7. К вершине v1 присоединим ребро с весом 2, соединяющее вершины v1 и v6. К вершине v6 присоединим ребро с весом 1, соединяющее вершины v6 и v3. Дале переходим от v3 к v8, вес ребра 2. Потом присоединяем ребро от вершины v7 к v4 с весом 4 и от вершины v4 к вершине v5 с весом 1. Таким образом, получаем следующее минимальное корневое дерево с весом, равным wmin(T) = 1 + 1 + 4 + 1 + 2 + 1 + 2 = 12.

Задача 2

В графе с помощью алгоритма Дейкстры найти кратчайший путь от вершины 2 ко всем остальным.

Решение

Вершине v2 присваиваем метку 0. Ее соседи v1, v6, v3, v7. Пометим их. Из вершины v2 в вершину v1 пути нет, так как граф ориентированный.

Вершине v4 присваиваем метку 8, так как min(7+2; 3+5) = 8.

Помечены все вершины, возле каждой указана длина пути из вершины v2.

 

Задача 3

Решение

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

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

Получили два критических пути:

Критический путь №1:(1,2)(2,3)(3,8)

Критический путь №2:(1,4)(4,6)(6,7)(7,8)Дляна кртического пути 13.

Резерв времени для операции v1 – v4 0, так как операция принадлежит критическому пути.

Для определения резервов времени по событиям сети рассчитывают наиболее ранние tp и наиболее поздние tп сроки свершения событий. Любое событие не может наступить прежде, чем свершаться все предшествующие ему события и не будут выполнены все предшествующие работы. Поэтому ранний (или ожидаемый) срок tp(i) свершения i-ого события определяется продолжительностью максимального пути, предшествующего этому событию:

tp(i) = max(t(Lni))

где Lni – любой путь, предшествующий i-ому событию, то есть путь от исходного до i-ого события сети.

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

tp(j) = max[tp(i) + t(i,j)]

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

tп(i) = tkp - max(t(Lci))

где Lci - любой путь, следующий за i-ым событием, т.е. путь от i-ого до завершающего события сети.

Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле:

tп(i) = min[tп(j) - t(i,j)]

Резерв времени R(i) i-ого события определяется как разность между поздним и ранним сроками его свершения:

R(i) = tп(i) - tp(i)

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

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

При определении ранних сроков свершения событий tp(i) двигаемся по сетевому графику слева направо и используем формулы (1), (2).

 

Работа (i,j)	Продолжительность tij	Ранние сроки: начало tijР.Н.	Ранние сроки: окончание tijР.О.	Поздние сроки: начало tijП.Н.	Поздние сроки: окончание tijП.О.	Резервы времени: полный RijП	Независимый резерв времени RijН	Частный резерв I рода, Rij1	Частный резерв II рода, RijC
(1,2)	4	0	4	0	4	0	0	0	0
(1,4)	6	0	6	0	6	0	0	0	0
(1,6)	4	0	4	7	11	7	7	7	7
(2,3)	5	4	9	4	9	0	0	0	0
(2,5)	4	4	8	7	11	3	0	3	0
(3,8)	4	9	13	9	13	0	0	0	0
(4,5)	2	6	8	9	11	3	0	3	0
(4,6)	5	6	11	6	11	0	0	0	0
(5,7)	1	8	9	11	12	3	0	0	3
(5,8)	2	8	10	11	13	3	0	0	3
(6,7)	1	11	12	11	12	0	0	0	0
(7,8)	1	12	13	12	13	0	0	0	0

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

R(i,j)= Rп(i,j) - R(i)

Частный резерв времени второго вида, или свободный резерв времени Rc работы (i,j) представляет собой часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Rc находится по формуле:

R(i,j)= Rп(i,j) - R(j)

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

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

R(i,j)= Rп(i,j)- R(i) - R(j)

В данном случае имеются несколько критических путей:

Критический путь №1:(1,2)(2,3)(3,8)

Критический путь №2:(1,4)(4,6)(6,7)(7,8)

Продолжительность критического пути: 13.

Задача 4

Найти максимальный поток в транспортной сети

Решение

Источник v1, сток – v6.

Решаем задачу методом Форда – Фалкерсона

Сток получил отметку (а5+;1), поэтому поток будет изменяться на 1 ед. При этом перешли к истоку,  поэтому процедура изменения потока закончена. Вытираем все отметки.

Вершине v2 отметку не присваиваем, так как 1 = 1. Для смежной с истоком вершины v3 присваиваем отметку (а1+;7).

Сток получил отметку (а4+;3), поэтому поток будет изменяться на 3 ед. При этом перешли к истоку,  поэтому процедура изменения потока закончена. Вытираем все отметки.

Для смежной с источником неотмеченной вершины v3 имеем что дуга направлена из v1 в v3, 3<7, поэтому присваиваем вершине v3 отметку (а1+; 4). Вершине v4 отметку не присваиваем, так как 3 = 3.

Отметили вершины, поток изменили на 1 ед.

Перешли к истоку, отметки вытираем.

Дуга v1 – v3 не насыщена, но следующие дуги (3 – 5) и (3 – 4) насыщены, дуга (1 – 2) также насыщена, на этом поиск завершаем.

Поток максимальной мощности в сети равен 5 – сумма потока по дугам, инцидентным истоку (стоку).