Лабораторна робота

на тему:

Теорія графів. Вирішення екстремальних задач за допомогою графів.

Для заданого графу відстані між столицями Європейських країн знайти
дерева максимальної та мінімальної ваги за допомогою алгоритму Краскао.

х1(

х6( (х2

х5( (х3

х4(

х1 = Столиця Словаччини – Братислава

х2 = Столиця Чехії — Прага

х3 = Столиця Австрії — Відень

х4 = Столиця Польщі — Варшава

х5 = Столиця Угорщини — Будапешт

х6 = Столиця Румунії – Бухарест

P (U1) = 7,56 P (U6 ) = 3,74 P (U11 ) = 11,21

P (U2) = 5,36 P (U7 ) = 3,16 P (U12 ) = 1,94

P (U3) = 0,67 P (U8 ) = 3,26 P (U13 ) = 6,7

P (U4) = 8,42 P(U9 ) = 1,14 P (U14 ) = 6,28

P (U5) = 9,12 P(U10)= 6,26 P (U15 ) = 5,26

Xi x1 x5 x1 x6 x6 x5 x5 x1 x1 x2 x2 x2 x3 x4 x1

Xj x6 x6 x5 x3 x4 x2 x3 x2 x3 x4 x6 x3 x4 x5 x4

P 7,5 5,3 0,6 8,4 9,1 3,7 3,1 3,2 1,1 6,2 11 1,9 6,7 6,2 5,2

min

UI = {x1,x5} x1(

UII = {x1,x5,x3} x6( (x2

UIII = {x1,x5,x3,x2}

UIV = {x1,x5,x3,x2,x4} x5( (x3

UV = {x1,x5,x3,x2,x4,x6} x4(

P = 0,6+1,1+1,9+6,2+9,1 = 18,9

max

UI = {x2,x6} x1(

UII = {x2,x6,x4} x6( (x2

UIII = {x2,x6,x4,x3}

UIV = {x2,x6,x4,x3,x1} x5( (x3

UV = {x2,x6,x4,x3,x1,x5} x4(

P = 11+9,1+8,4+7,5+5,3 = 41,3

Для заданого графу відстані між столицями Європейських країн знайти
дерева максимальної та мінімальної ваги за допомогою алгоритму Прима.

max

x\x x1 x2 x3 x4 x5 x6

x1 0 3,2 1,1 5,2 0,6 7,5

x2 3,2 0 1,9 6,2 3,7 11

x3 1,1 1,9 0 6,7 3,1 8,4

x4 5,2 6,2 6,7 0 6,2 9,1

x5 0,6 3,7 3,1 6,2 0 5,3

x5 7,5 11 8,4 9,1 5,3 0

x1 x2 x3 x4 x5 x6

S 0 3,2 1,1 5,2 0,6 7,5

I 1 1 1 1 1 1

S x 3,2 8,4 9,1 5,3 x

I 1 1 6 6 6 1

S x 6,2 8,4 x 6,2 x

I 1 4 6 6 4 1

S x 6,2 x x 6,2 x

I 1 4 6 6 4 1

S x x x x 6,2 x

I 1 4 6 6 4 1

P = 7,5+9,1+8,4+6,2+6,2 =37,4

x1(

x6( (x2

x5( (x3

x4(

min

x\x x1 x2 x3 x4 x5 x6

x1 ( 3,2 1,1 5,2 0,6 7,5

x2 3,2 ( 1,9 6,2 3,7 11

x3 1,1 1,9 ( 6,7 3,1 8,4

x4 5,2 6,2 6,7 ( 6,2 9,1

x5 0,6 3,7 3,1 6,2 ( 5,3

x5 7,5 11 8,4 9,1 5,3 (

x1 x2 x3 x4 x5 x6

S ( 3,2 1,1 5,2 0,6 7,5

I 1 1 1 1 1 1

S x 3,2 1,1 5,2 x 5,3

I 1 1 1 1 1 5

S x 1,9 x 5,2 x 5,3

I 1 3 1 1 1 5

S x x x 5,2 x 5,3

I 1 3 1 1 1 5

S x x x x x 5,3

I 1 3 1 1 1 5

P = 0,6+1,1+1,9+5,2+5,3 = 14,1

x1(

x6( (x2

x5( (x3

x4(

Похожие записи