Алгоритмы путей

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ

Кафедра «Прикладная математика»

Контрольная работа по дисциплине «Дискретная математика»

Выполнил: Кузнецов Е.П.

Проверил: к.ф.-м.н., доцент Симонов Б. В.

Волгоград, 2018



Задание 1

По заданной матрице весов ? графа G найти величины минимального пути и сам путь от вершины s = x1 до вершины t = x6 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами.

	x1	x2	x3	x4	x5	x6
x1	-	10	12	?	?	?
x2	?	-	11	9	?	19
x3	?	?	-	?	10	?
x4	?	?	13	-	11	10
x5	?	?	?	?	-	6
x6	?	?	?	?	?	-

Этап 1 - нахождение длин минимального пути

Шаг 1

Полагаем d(x₁)=0*, x Ю=x₁

d(x₂)= d(x₃)= d(x₄)= d(x₅)= d(x₆)= ?

1 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной x Ю=x₁ с временными метками

S Ю={x₂, x₃}

Пересчитаем временные метки этих вершин

d(x₂)=min {?, 0*+10}=10

d(x₃)=min {?, 0*+12}=12

Шаг 3

Одна из временных меток превращается в постоянную

Min { x₂, x₃, x₄, x₅, x₆}= min {10, 12, ?, ?, ?} = 10*= d(x₂)

Полагаем x Ю=x₂

Шаг4

Возврат на 2 шаг

2 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной с временными метками

S Ю={x₃, x₄, x₆}

Пересчитаем временные метки этих вершин

d(x₃) = min {?, 10*+11)=21

d(x₄)=min{?,10*+9)=19

d(x₆)=min{?,10*+19)=29

Шаг 3

Одна из временных меток превращается в постоянную

Min {x₃,x₄,x₅,x₆}=min{12,19, ?,29)=12*=d(x₃)

Шаг 4

Возврат на 2 шаг

3 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной с временными метками

??Ю={x₅}

Пересчитаем временные метки этих вершин

d(x₅)= min {12+10}= 22

Шаг 3

Одна из временных меток превращается в постоянную

Min {x₄,x₅,x₆}=min{19,22,29) = 19*=d(x₄)

Полагаем ??Ю=x₄

Шаг 4

4 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной ??Ю=x₄ с временными метками

??Ю={x₃,x₅,x₆}

Пересчитаем временные метки этих вершин

d(x₃)=min{12,19*+13}=12

d(x₅)=min{22,19*+11}=22

d(x₆)=min{29,19*+10}=29

Шаг 3

Одна из временных меток превращается в постоянную

Min {x₃,x₅,x₆}=12*=d(x₃)

Полагаем

Шаг 4

??Ю=x3 ? t=x6

Возврат на 2 шаг

5 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной с временными метками

??Ю={x₅}

Пересчитаем временные метки этих вершин

d(x₅)= min {12+10}= 22

Шаг 3

Одна из временных меток превращается в постоянную

Min {x₅,x₆}=min{22,29) = 22*=d(x₅)

Полагаем ??Ю=x₅

Шаг 4

6 Итерация

Шаг 2

Множество вершин, непосредственно следующих за вершиной с временными метками

??Ю={x₆}

Пересчитаем временные метки этих вершин

d(x₆)=min{22+6}=28

Шаг 3

Одна из временных меток превращается в постоянную

Min {x₆}=28*=d(x₆)

Полагаем ??Ю=x₆

Шаг 4

Конец 1 этапа

Этап 2 - построение кратчайшего пути

1 Итерация

Шаг 5

Составим множество вершин, непосредственно предшествующих x Ю=x₆ с постоянными метками

S Ю={x₂,x₄,x₅}

=28*?10*+19=d(x₂)+ щ(x₂, x₆)

d(x Ю)=28*?19*+10 = d(x₄)+щ(x₄, x₆)

d(x Ю)=28*= 22*+6 = d(x₅)+щ(x₅, x₆)

Включаем дугу щ(x₅, x₆) в кратчайший путь

Полагаем x Ю=x₅

Шаг 6

Возврат на 5 шаг

3 Итерация

Шаг 5

Составим множество вершин, непосредственно предшествующих x Ю=x₅ с постоянными метками

S Ю={x₃,x₄}

d(x Ю)=22* ? 19*+11 = d(x₄)+щ(x₄, x₅)

d(x Ю) =22*= 12*+10 = d(x2)+щ(x₃, x₅)

Включаем дугу щ(x₃, x₅) в кратчайший путь

Полагаем x Ю=x₃

Шаг 6

Возврат на 5 шаг

4 Итерация

Составим множество вершин, непосредственно предшествующих x Ю=x₃ с постоянными метками

S Ю={x₁,x₂,x₄}

d(x Ю) = 12* ? 10*+11 = d(x₂)+щ(x₂, x₃)

d(x Ю) = 12* ? 19*+13 = d(x₄)+щ(x₄, x₃)

d(x Ю) = 12* = 0*+12 = d(x₁)+щ(x₁, x₃)

Включаем дугу щ(x₁, x₃) в кратчайший путь.

Полагаем x Ю=x1

Шаг 6

Завершение 2 этапа

Кратчайший путь от x₁ до x₆ построен, его длинна составляет 12+10+6=28

Данный путь образован последовательностью дуг

µ= щ(x₁, x₃)- щ(x₃, x₅)- щ(x₅, x₆)

Нахождение максимального пути

Упорядочи вершины по алгоритму Фолкерсона

1.Вершина x₁ не содержит входящих дуг, вследствие чего вычеркнем все дуги, исходящие из этой вершины, вершину отнесем в группе 1.

2.Вершина x₂ не содержит входящих дуг, вследствие чего вычеркнем все дуги, исходящие из этой вершины, вершину отнесем к группе 2.

3. Вершина x₄ не содержит входных дуг, вследствие чего вычеркнем все дуги, исходящие из этой вершины, вершину отнесем к группе 3.

4.Вершина x₃ не содержит входных дуг, вследствие чего вычеркнем все дуги, исходящие из этой вершины, вершину отнесем к группе 4.

5. Остались только вершины x₅ и x₆, относим их к группам 5 и 6 соответственно.

Упорядоченные вершины:

d1=0

d2=max(d1+10)=max(0+10)=10

d3=max(d2+9)=max(10+9)=19

d4=max(d1+12,d2+11,d3+13)=(0+12,10+11,19+13)=32

d5=max(d3+11,d4+10)=(19+11,32+10)=42

d6=max(d2+19,d3+10,d5+6)=(10+19,19+10,42+6)=48

Длина максимального пути из x₁ в x₆ равна 48

Этап 2 - нахождение максимального пути

x₆:

d₆=48=d₅+6=48

d₆=48?d₂+19=29

d₆=48?d₃+10=29

Включаем дугу (x₅,x₆) в максимальный путь.

x₅:

d₅=42=d₄+10=42

d₅=42?d₃+11=30

Включаем дугу (x₃,x₅) в максимальный путь.

x₃:

d₄=32=d₃+13=32

d₄=32?d₁+12=12

d₄=32?d2+11=21

Включаем дугу (x₄,x₃) в максимальный путь.

x₄:

d₃=19=d₂+9=19

Включаем дугу (x₂,x₄) в максимальный путь.

x₂:

d₂=10=d₁+10=10

Включаем дугу (x₁,x₂) в максимальный путь.

Максимальный путь:

µ_max=(x₁,x₂)-(x₂,x₄)-(x₄,x₃)-(x₃,x₅)-(x₅,x₆)

Задание 2

По заданной матрице весов ? графа G найти минимальный путь по алгоритму Беллмана-Мура между начальной вершиной s = x1 и конечной вершиной t = x7.

	x1	x2	x3	x4	x5	x6	x7
x1	-	?	8	?	?	?	?
x2	?	-	?	?	-6	10	12
x3	?	4	-	-4	?	-7	?
x4	?	?	?	-	?	?	3
x5	?	?	7	10	-	6	?
x6	?	?	?	8	?	-
x7	?	?	?	?	?	?	-

Этап 1 - нахождение длин кратчайших путей от вершины s до всех остальных вершин графа

Шаг 1

x Ю=x1;

d(x₁)=0

d(xj)= ?;

Q = {x1}

1 Итерация

Шаг 2

x Ю=x1; тогда Q=Q\{x₁}= Ш

Пусть S Ю - множество вершин, непосредственно достижимых из x Ю.

S Ю={x₃}

d(x₃)=min{?,0+8}=8

8<?? Да Q={x3}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

2 Итерация

Шаг 2

x Ю=x₃; Тогда Q=Q\{ x Ю}= Ш

S Ю={x₂,x₄,x₆}

d(x₂)=min{?,8+4}=12

12<?? Да Q={x₂}

d(x₄)=min{?,8-4}=4

4<?? Да Q={x₂,x₄}

d(x₆)=min{?,8-7}=1

1<?? Да Q={x₂,x₄,x₆}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

3 Итерация

Шаг 2

x Ю=x₂; Тогда Q=\{ x Ю}={x₄,x₆}

S Ю={x₅,x₆,x₇}

d(x₅)=min(?,12-6)=6

6<?? Да Q={x₄,x₅,x₆}

d(x₆)=min(1,12+10)=22

22<1?Нет Q={x₄,x₅,x₆}

d(x₇)=min(?,12+12)=24

24<?? Да Q={x₄,x₅,x₆,x₇}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

4 Итерация

Шаг 2

x Ю=x4; Тогда Q=Q\{ x Ю}={x₅,x₆,x₇}

S Ю={x₆}

d(x₆)=min(1,4+3)=7

7<1? Нет Q={x₅,x₆,x₇}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

5 Итерация

Шаг 2

x Ю=x₅; Тогда Q=Q\{ x Ю}={x₆,x₇}

S Ю={x₃,x₄,x₆}

d(x₃)=min(8,6+7)=13

13<8? Нет Q={x₆,x₇}

d(x₄)=min(4,6+10)=16

16<4? Нет Q={x₆,x₇}

d(x₆)=min(1,6+6)=12

12<1? Нет Q={x₆,x₇}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

6 Итерация

Шаг 2

x Ю=x₆; Тогда Q=Q\{ x Ю}={x₇}

S Ю={x₄,x₇}

d(x₄)=min(4,1+8)=9

9<4? Нет Q={x₇}

d(x₇)=min(24,1+5)=6

6<24? Да Q={x₇}

Шаг 3

Q = Ш? Нет. Переход на начало 2 шага.

7 Итерация

Шаг 2

x Ю=x7; тогда Q = Q\{x Ю} = Ш

S Ю=Ш

Шаг 3

Q = Ш? Да. Конец 1 этапа.

2 Этап - нахождение кратчайшего пути

Шаг 4

x Ю=x₇

Пусть S Ю - множество вершин, непосредственно предшествующих вершине x Ю

S Ю={x₆,x₂}

1 Итерация

Шаг 5

d(x Ю) = 6 =1+5= d(x₆)+щ(x₆, x₇)

d(x Ю) = 6 ? 12+12 = d(x₂)+щ(x₂, x₇)

Включаем дугу щ(x₆, x₇) в кратчайший путь

Шаг 6

x Ю ? s=x₁

Возврат на 5 шаг

2 Итерация

Шаг 5

S Ю={x₂,x₃,x₄,x₅}

d(x Ю) = 1 ? 12+10 = d(x₂)+щ(x₂, x₆)

d(x Ю) = 1 =8-7 = d(x₃)+щ(x₃, x₆)

d(x Ю) = 1 ? 4+3 = d(x₄)+щ(x₄, x₆)

d(x Ю) = 1 ? 6+6 = d(x₅)+щ(x₅, x₆)

Включаем дугу щ(x₃, x7) в кратчайший путь

Шаг 6

x Ю ? s=x₁

Возврат на 5 шаг

3 Итерация

Шаг 5

S Ю={x₁}

d(x Ю) = 8 =0+8 = d(x₁)+щ(x₁, x₃)

Включаем дугу щ(x₁, x₃) в кратчайший путь

Шаг 6

x Ю=s=x1

Завершение 2 этапа

Кратчайший путь от x₁ до x₇ построен.

Длина пути = 8+(-7)+5=6

Путь образован последовательностью:

(x₁,x₃)-(x₃,x₆)-(x₆,x₇)

Задание 3

Для графа G, заданного матрицей весов, построить минимальный по весу остов G' и найти его вес.

	X1	X2	X3	X4	X5	X6	X7
X1	-	8	9	?	?	?	6
X2	8	-	7	6	9	?	?
X3	9	7	-	6	10	5	?
X4	?	6	6	-	8	7	?
X5	?	9	10	8	-	4	5
X6	?	?	5	7	4	-	6
X7	6	?	?	?	5	6	-

Шаг 1

Полагаем S'={x₃}, S''={x₁,x₂,x₄,x₅,x₆,x₇}

V? = Ш

1 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₄), щ(x₃,x₅), щ(x₃,x₆)}= min {9,7,6,10,5)=5= щ(x₃,x₆)

S'={x3,x6},S''={x₁,x₂,x₄,x₅,x₇}

V'={(x₃,x₆)}

Шаг 3

S? ? S

Переход на начало 2 шага

2 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₄), щ(x₃,x₅), щ(x₆,x₅), щ(x₆,x₇)}=min{9,7,6,10,4,6}=4= щ(x₆,x₅)

S'={x₃,x₅,x₆},S''={x₁,x₂,x₄,x₇}

V'={(x₃,x₆),(x₆,x₅)}

Шаг 3

S? ? S

Переход на начало 2 шага

3 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₄), щ(x₃,x₅), щ(x₆,x₇), щ(x₅,x₂), щ(x₅,x₄),(x₅,x₇)}=min{9,7,6,10,6,9,8,5}=5= щ(x₅,x₇)

S'={x₃,x₅,x₆,x₇},S”={x₁,x₂,x₄}

V'={(x₃,x₆),(x₆,x₅),(x₅,x₇)}

Шаг 3

S? ? S

Переход на начало 2 шага

4 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₄), щ(x₃,x₅), щ(x₅,x₂), щ(x₅,x₄), щ(x₇,x₁)}={9,7,6,10,9,8,5,6}=6= щ(x₇,x₁)

S'={x₁,x₃,x₅,x₆,x₇},S''={x₂,x₄}

V'={(x₃,x₆),(x₆,x₅),(x₅,x₇),(x₇,x₁)}

Шаг 3

S? ? S

Переход на начало 2 шага

5 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₄), щ(x₃,x₅), щ(x₅,x₂), щ(x₅,x₄), щ(x₁,x₂)}=min{9,7,6,10,9,8,5,8}=6= щ(x₃,x₄)

S'={x₁,x₃,x₄,x₅,x₆,x₇}, S''={x2}

V'={(x₃,x₆),(x₆,x₅),(x₅,x₇),(x₇,x₁),(x₃,x₄)}

Шаг 3

S? ? S

Переход на начало 2 шага

6 Итерация

Шаг 2

d(S',S'')=min{ щ(x₃,x₁), щ(x₃,x₂), щ(x₃,x₅), щ(x₅,x₂), щ(x₅,x₄), щ(x₁,x₂), щ (x₄,x₂), щ (x₄,x₆)}= min{9,7,10,9,8,5,8,6,7}=6= щ(x₄,x₂)

S'={x₁,x₂,x₃,x₄,x₅,x₆,x₇}, S''= Ш

V'={(x₃,x₆),(x₆,x₅),(x₅,x₇),(x₇,x₁),(x₃,x₄),(x₄,x2)}

Шаг 3

Получим основной граф G'=(S',V').

Вес графа = 6+5+4+5+6+6=32

Задание 4

матрица алгоритм путь

По заданной матрице пропускных способностей дуг ? графа G найти максимальный поток от вершины s=x1 до вершины t=x7 и указать минимальный разрез, отделяющий s от t

	x1	x2	x3	x4	x5	x6	x7
x1	-	7	9	-	-	8	-
x2	-	-	11	14	10	-	6
x3	-	-	-	9	11	19	-
x4	-	-	-	-	-	12	-
x5	-	-	-	8	-	14	-
x6	-	-	-	-	-	-	10
x7	-	-	-	-	-	-	-

Этап 1

Д=min{7;6}=6

Дуга (x₂,x₇) - насыщенная

Д=min{9,19,10}=9

Дуга (x₁,x₃) - насыщенная

Д=min{8,10-9}=1

Дуга (x₆,x₇) - насыщенная

Более маршрутов нет, поток максимальный

Делаем разрез вокруг t.

Максимальный поток:16

Размещено на Allbest.ru

...