Головна Головна -> Інше українською -> Економічні теми -> Теорія графів. Вирішення екстремальних задач за допомогою графів.

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

Назва:
Теорія графів. Вирішення екстремальних задач за допомогою графів.
Тип:
Інше
Мова:
Українська
Розмiр:
0,91 KB
Завантажень:
340
Оцінка:
 
поточна оцінка 5.0


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


Для заданого графу відстані між столицями Європейських країн знайти дерева максимальної та мінімальної ваги за допомогою алгоритму Краскао.
х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

Завантажити цю роботу безкоштовно



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок