UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваТеорія графів. Вирішення екстремальних задач за допомогою графів (лабораторна)
Авторdimich
РозділМіжнародні відносини, ЗЕД, міжнародна економіка
ФорматWord Doc
Тип документуЛабораторна робота
Продивилось494
Скачало129
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

на тему:

 

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

 

 

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

дерева максимальної та мінімальної ваги за допомогою алгоритму Краскао.

 

х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(

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ