Лабораторна робота
на тему:
Теорія графів. Вирішення екстремальних задач за допомогою графів.
Для заданого графу відстані між столицями Європейських країн знайти
дерева максимальної та мінімальної ваги за допомогою алгоритму Краскао.
х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(
Нашли опечатку? Выделите и нажмите CTRL+Enter
