Дискретная математика. Лаба №2 Дискр матемм. Лабораторная работа 2 по дисциплине Дискретная математика вариант 11 Задание 1

• Название: Лабораторная работа 2 по дисциплине Дискретная математика вариант 11 Задание 1
• Анкор: Дискретная математика
• Дата: 08.05.2022
• Размер: 0.9 Mb.
• Имя файла: Лаба №2 Дискр матемм.docx
• Тип: Лабораторная работа; #517467

учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра компьютерных систем в управлении

и проектировании (КСУП)
ОТЧЕТ

Лабораторная работа № 2
по дисциплине

«Дискретная математика»

вариант 11

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

Исходные данные:

вершина х0 – начальная;

вершина х7 – конечная.

r[0,1] = 12 r[4,7] = 34 r[6,3] = 13 r[5,7] = 43

r[0,2] = 10 r[4,2] = 18 r[6,7] = 35 r[5,4] = 46

r[0,3] = 29 r[2,5] = 21 r[2,1] = 3 r[6,5] = 11

r[1,4] = 25 r[2,6] = 15 r[3,2] = 32
Построим граф (рис.1)



За текущую рассматриваемую вершину с постоянной пометкой возьмем вершину X0

Присвоим L(X0)=0 L(Xi)=  (рис.2)


Найдем прямое отображение для текущей рассматриваемой вершины X0 это будут вершины X1, X2 X3.

Все вершины, входящие в прямое отображение имеют временные пометки, поэтому пересчитаем их значение:

L(X1)min(  ; 0+12)=12 заменяем метку

L(X2)min(  ; 0+10)=10 заменяем метку

L(X3)min(  ; 0+29)=29 заменяем метку

Имеем следующие метки вершин:

L(X1)=12 L(X5)=

L(X2)=10 L(X6)=

L(X3)=29 L(X7)=

L(X4)=

Очевидно, что минимальную метку, равную 10, имеет вершина X2.

За следующую текущую метку принимаем вершину X2, а метка X0 становится постоянной (рис 3).


Найдем прямое отображение для текущей рассматриваемой вершины X2 это будут вершины X0, X1, X6 X3 X4. Все вершины, кроме X0, входящие в прямое отображение имеют временные пометки, поэтому пересчитаем их значение:

L(X1)min(  ; 10+3)=12 оставляем метку

L(X4)min(  ; 10+18)=28 заменяем метку

L(X3)min(  ; 10+32)=29 оставляем метку

L(X6)min(  ; 10+15)=25 заменяем метку


Имеем следующие метки вершин:

L(X1)=12

L(X3)=29

L(X4)=
L(X6)=
L(X5)=
L(X7)=


Помечаем Х2 как рассмотренную (рис.4).

Найдем прямое отображение для текущей рассматриваемой вершины X1, это будут вершины X0, X2,X4. Для X0, X2 метки постоянные. Для X4 временные метки поэтому рассчитаем

L(X4)min(  ; 12+25)=28 оставляем метку. Помечаем X1 как рассмотренную (рис.5)



Рис.5
Перейдем к вершине X3. Найдем прямое отображение для текущей рассматриваемой вершины X3,: X0, X2,X6. Для X0, X2 метки постоянные. Для X6 временные метки поэтому рассчитаем L(X6)min(  ; 13+29)=25 оставляем метку.

Имеем следующие временные метки

L(X3)=29

L(X4)=
L(X6)=
L(X5)=
Помечаем X3 как рассмотренную (рис.6)



Рис.6
Перейдем к вершине X6 Найдем прямое отображение для текущей рассматриваемой вершины X6, это будут вершины X2, X3,X5 X7 Для X3, X2 метки постоянные. Для X5, X7 рассчитаем их значения.
L(X5)min(  ; 11+25)=36 заменяем метку
L(X7)min(  ; 35+25)=60 заменяем метку
Имеем следующие временные метки

L(X5)= 36
L(X7)=
L(X4)=
Все смежные вершины рассмотрены помечаем вершину X6 как рассмотренную (рис.7)



Рис.7.
Перейдем к вершине X5. Найдем прямое отображение для текущей рассматриваемой вершины X5 это буду вершины X4,X6, X7 Для X6 метка постоянная. Для X4, X7 рассчитаем их значения.
L(X4)min(  ; 36+46)=28 оставляем метку
L(X7)min(  ; 36+43)=60 оставляем метку
L(X4)=
L(X5)=
L(X7)=
Все вершины рассмотрены, помечаем оставшиеся вершины: X4,X5, X7, как рассмотренные (рис.8)



Рис.8

Все вершины имеют постоянные метки, алгоритм окончен.
Для нахождения кратчайшего пути между вершинами X0 и X7.

Для построения кротчайшего маршрута пройдем обратный путь от X7 к X0. X7 последовательно используем соотношение L(x*i)+c( x*i, xi)=L( xi), где L( xi) - пометка рассматриваемой вершины , L(x*i) - пометка предшествующей вершины вершине xi, с - вес ребра соединяющий вершины x*i и вершину хi ,).

L(X7)=60
L(X5)+c(X5, X7)=36+43  L(X7)

L(X6)+c(X6, X7)=35+25= L(X7)

Это означает, что в вершину, X7 мы попали из вершины X6.

L(X6)=25

L(X3)+c(X3, X6)=13+29  L(X6)

L(X2)+c(X2, X6)=10+15=L(X6)

В вершину, X6 мы попали из вершины X2. В свою очередь из вершины X2 мы попали из вершины X1, так как 10 минимальное значение.

Ответ: кротчайший путь из X0 в X7 имеет длину 60 и проходит по вершинам: X0, X2, X6, X7.


Задание 2. 

Решить задачу о коммивояжере.
Исходные данные к задаче нахождения гамильтонова цикла в графе (задача о коммивояжере) представлены в приложении Д.
Значенияэлементовматрицырасстояний:

a(1.1) =   a(2.1) = 53 a(3.1) = 32 a(4.1) = 11 a(5.1) = 22

a(1.2) = 95 a(2.2) =   a(3.2) = 72 a(4.2) = 35 a(5.2) = 3

a(1.3) = 15 a(2.3) = 24 a(3.3) =   a(4.3) = 29 a(5.3) = 34

a(1.4) = 13 a(2.4) = 36 a(3.4) = 18 a(4.4) =   a(5.4) = 16

a(1.5) = 46 a(2.5) = 75 a(3.5) = 24 a(4.5) = 38 a(5.5) = 
Решение:
Составим таблицу длин ребер

∞	95	15	13	46
54	∞	24	36	75
32	72	∞	18	24
11	35	29	∞	38
22	3	34	16	∞

Выберем минимальный элемент в каждой строке и вычтем его из каждого элемента соответствующей строке.

∞	95	15	13	46	13
53	∞	34	36	75	24
32	72	∞	18	24	18
11	35	29	∞	38	11
22	3	34	16	∞	3

Вычтем

∞	95	15	0	46
53	∞	0	36	75
32	72	∞	0	24
0	35	29	∞	38
22	0	34	16	∞

В пятом столбце нет нуля, минимальный элемент этого столбца равен 24, вычтем его из всего столбца.

∞	95	15	0	22
53	∞	0	36	51
32	72	∞	0	0
0	35	29	∞	14
22	0	34	16	∞

Полученная матрица содержит нули в каждом столбце и каждой строке. Попробуем по ним составить путь коммивояжера ( гамильтонов цикл)

1) Элемент (5;2)=0, убираем пятую строку и первый столбец.

∞	95	15	0	22
53	∞	0	36	51
32	72	∞	0	0
0	35	29	∞	14
22	0	34	16	∞

2) Элемент (4;1)=0, убираем четвертую строку и пятый столбец.

∞	95	15	0	22
53	∞	0	36	51
32	72	∞	0	0
0	35	29	∞	14
22	0	34	16	∞

3) Элемент (3;5)=0, убираем третью строку и четвертый столбец.

∞	95	15	0	22
53	∞	0	36	51
32	72	∞	0	0
0	35	29	∞	14
22	0	34	16	∞

4) Элемент (2;3)=0, убираем вторую строку и третий столбец.

∞	95	15	0	22
53	∞	0	36	51
32	72	∞	0	0
0	35	29	∞	14
22	0	34	16	∞

5) Остается только элемент (1;4)=0.


Ответ: получили гамильтонов цикл (5;2) (4;1) (3;5) (2;3) (1;4).

13 + 24 + 24 + 11 + 3 = 75 – длина пути.

Задание 3. 
Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда – Фалкерсона.

Исходные данные:
Дана сеть S(X,U)
x0 – исток сети; x7 – сток сети, где x0   X; x7   X.

Значения пропускной ri,j способности дуг сети представлены в приложении Е. 

Задание:
1. Вычислить значение максимального потока на сети S, применяя алгоритм Форда – Фалкерсона.
2. Построить разрез сети S.
Примечание
Значения пропускных способностей дуг ri,j заданы по направлению ориентации дуг: от индекса i к индексу j.


ВАРИАНТ 11
[0,1] = 32 r[4,7] = 4 r[6,3] = 13 r[5,7] = 43

r[0,2] = 84 r[4,2] = 18 r[6,7] = 35 r[5,4] = 26

r[0,3] = 91 r[2,5] = 21 r[2,1] = 73 r[6,5] = 61

r[1,4] = 25 r[2,6] = 15 r[3,2] = 32

	0	1	2	3	4	5	6	7
0	0	32	84	91	0	0	0	0
1	0	0	0	0	25	21	15	0
2	0	73	0	0	0	0	0	0
3	0	0	32	0	0	0	0	0
4	0	0	18	0	0	0	0	4
5	0	0	0	0	26	0	0	43
6	0	0	0	13	0	61	0	35
7	0	0	0	0	0	0	0	0

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток — это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.


911
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:

X0-X1-X5-X7



Находим min (32,21,43)=21 и увеличиваем поток на эту величину. Ребро Х1-Х5 помечаем как рассмотренное. 

Выбираем еще один путь, X0-X3-X2-X1-X4-X7

Находим min (91,32,73,25,4)=4 и увеличиваем поток на эту величину. Ребро Х4-Х7 помечаем как рассмотренное.


Выбираем еще один путь, X0-X1-X6-X7 Находим min (32,15,35)=15 и увеличиваем поток на эту величину. Ребро Х1-Х6 помечаем как рассмотренное


6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 21+15+4=40.Вывод: максимальный поток равен 40.

Суммарный поток, заходящий в любую вершину сети(кроме истока и стока), равен суммарному потоку, выходящему из этой вершины: +(f ) = −( f) для каждой внутренней вершины x.

Проведем проверку баланса на насыщенной сети

К примеру возьмем вершину 4 входящие 25 и 0 выходящие 4 и 8, баланс соблюден.
2) Построить разрез сети S. Процедура «пометок вершин». Начальное состояние: все вершины не имеют пометок. Вершине 0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются помет (красные круги)


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

Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы — в непомеченных вершинах.
Это дуги:U_1,6 ,U_1,5, U_4,7
Таким образом, минимальный разрез данной сети T= (U_1,6 ,U_1,5, U_4,7)

Ответ: Ф_max =40; T= (U_1,6 ,U_1,5, U_4,7).
Задание 4. 

Выполнить минимизацию булевой функции с помощью карты Карно.

Варианты булевой функции представлены в приложении Ж.

f(x,y,z) = x¬ y z  ¬(x y)z  x ¬(y z)  x y ¬z  xyz  xyz.

Составим таблицу истинности для данной формулы.

x

y

z

¬y

x∧¬y

x∧¬y∧z

x∧y

¬x∧y

¬x∧y∧z

x∧¬y∧z∨¬x∧y∧z

y∧z

0	0	0	1	0	0	0	1	0	0	0
0	1	0	0	0	0	0	1	0	0	0
0	1	1	0	0	0	0	1	1	1	1
0	1	1	0	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	0	0	0
1	0	1	1	1	1	0	1	1	1	0
1	1	0	0	0	0	1	0	0	0	0
1	1	1	0	0	0	1	0	0	0	1

Построим диаграмму Карно по полученной таблице истинности, подставляя

единицы в нужные ячейки.

Y  Z X	00	01	11	10
0	0	1	1	0
1	1	1	1	1

Выделим на карте Карно прямоугольные области из единиц наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им конъюнкции:

¬y∧z	x∧¬y∧z	x∧¬y∧z∨¬x∧y∧z∨x∧¬y∧z	¬z	x∧y∧¬z	x∧¬y∧z∨¬x∧y∧z∨x∧¬y∧z∨x∧y∧¬z	x∧y∧z	x∧¬y∧z∨¬x∧y∧z∨x∧¬y∧z∨x∧y∧¬z∨x∧y∧z	x∧¬y∧z∨¬x∧y∧z∨x∧¬y∧z∨x∧y∧¬z∨x∧y∧z∨x∧y∧z
1	0	0	0	1	0	0	1	0
1	1	1	0	1	0	1	0	0
1	0	0	0	1	0	0	1	0
1	1	1	1	0	0	1	0	0
1	0	0	0	1	1	1	1	0
1	1	1	0	1	1	1	0	0
0	0	0	0	1	1	1	1	1
0	0	0	1	0	0	0	0	0

K1: x
K₂: z
Объединим их с помощью операции ИЛИ и получим минимизированную ДНФ:

x∨z

Ответ: x∨z