WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМіжнародні відносини, Міжнародна економіка → Теорія графів. Вирішення екстремальних задач за допомогою графів (лабораторна) - Реферат

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


Лабораторна робота
на тему:
Теорія графів. Вирішення екстремальних задач за допомогою графів.
1. Для заданого графу відстані між столицями Європейських країн знайти дерева максимальної та мінімальної ваги за допомогою алгоритму Краскао.
х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
2. Для заданого графу відстані між столицями Європейських країн знайти дерева максимальної та мінімальної ваги за допомогою алгоритму Прима.
max
xx 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
xx 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"
Loading...

 
 

Цікаве