Теорія графів. Формування графічних моделей. Об’єкт модулювання: Європейська безпека за 2000 р. (лабораторна)

Язык: украинский
Тип документа: Word Doc
0 1159
Скачать документ

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

на тему:

Теорія графів. Формування графічних моделей.

Об’єкт модулювання: Європейська безпека за 2000 р.

Обрати 6 будь-яких країн Європи.

Мною було обрано такі країни:

Словаччина (х1)

Чехія (х2)

Австрія (х3)

Польща (х4)

Угорщина (х5)

Румунія (х6)

Побудувати граф-відношення спільні кордони.(граф #1)

х1(

х6( (х2

х5( (х3

х4(

Використовуючи формулу могутності описати кожну країну

де:

N – кількість населення (у млн. чоловік) (1)

G – кількість ВВП на душу населення (у млн. доларів) (2)

W – витрата на зброю(у млн. доларів) (3)

= 0,8.

Отже,

Р Словаччини = 5414,9 0,38 * 11243 0,62 * 357 0,8 = 938525

Р Чехії = 10264 0,38 * 13991 0,62 * 1175 0,8 = 3554322

Р Австрії = 8150,8 0,38* 26765 0,62 * 2131 0,8 = 7838167

Р Польщі = 38633,9 0,38 * 9051 0,62 * 3144 0,8 = 9867018

Р Угорщини = 10106 0,38 * 12416 0,62 * 715 0,8 = 2205228

Р Румунії = 22364 0,38 * 6423 0,62 * 541 0,8 = 1585565

Використовуючи Р, побудувати повний симетричний граф (граф #2) за
критерієм Р (Р – вага вершини).

х1(

х6( (х2

х5( (х3

х4(

P x1 = 938525 P x4 = 9867018

P x2 = 3554322 P x5 = 2205228

P x3 = 7838167 P x6 = 1585565

Побудувати орграф загрози.(граф #3)

х1(

х6( (х2

х5( (х3

х4(

Побудувати орграф безпосередньої загрози.(граф #4)

х1(

х6( (х2

х5( (х3

х4(

Побудувати для усіх заданих вище графів (1-4) матриці інцидентності.

Граф #1

x\u U1 U2 U3 U4 U5 U6 U7 U8

x1 0 1 0 0 0 1 1 0

x2 0 0 0 0 0 1 1 1

x3 0 0 1 0 0 1 0 1

x4 0 0 0 1 1 0 0 0

x5 1 1 1 0 0 0 0 0

x6 1 0 0 0 0 0 0 0

Граф #2

x\U U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U15

x1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1

x2 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0

x3 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0

x4 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1

x5 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0

x6 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0

Граф #3

x\U U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U15

x1 -1 0 -1 0 0 0 0 1 -1 0 0 0 0 0 -1

x2 0 0 0 0 0 -1 0 -1 0 -1 -1 -1 0 0 0

x3 0 0 0 1 0 0 1 0 1 0 0 1 -1 0 0

x4 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1

x5 0 1 1 0 0 1 -1 0 0 0 0 0 0 -1 0

x6 1 -1 0 -1 -1 0 0 0 0 0 1 0 0 0 0

Граф #4

x/x U1 U2 U3 U4 U5 U6 U7 U8

x1 0 -1 0 0 0 -1 1 0

x2 0 0 0 0 0 -1 -1 -1

x3 0 0 1 0 0 1 0 1

x4 0 0 0 1 1 0 0 0

x5 1 1 -1 0 0 0 0 0

x6 -1 0 0 0 0 0 0 0

Побудувати для усіх заданих вище графів матриці суміжності.

Граф #1

x/x x1 x2 x3 x4 x5 x6

x1 0 1 1 1 1 0

x2 1 0 1 1 0 0

x3 1 1 0 0 1 0

x4 1 1 0 0 0 0

x5 1 0 1 0 0 1

x6 0 0 0 0 1 0

Граф #2

x/x x1 x2 x3 x4 x5 x6

x1 0 1 1 1 1 1

x2 1 0 1 1 1 1

x3 1 1 0 1 1 1

x4 1 1 1 0 1 1

x5 1 1 1 1 0 1

x6 1 1 1 1 1 0

Графу #3

x/x x1 x2 x3 x4 x5 x6

x1 0 1 -1 -1 -1 -1

x2 -1 0 -1 -1 -1 -1

x3 1 1 0 -1 1 1

x4 1 1 1 0 1 1

x5 1 1 -1 -1 0 1

x6 1 1 -1 -1 -1 0

Графу #4

x/x x1 x2 x3 x4 x5 x6

x1 0 1 -1 -1 -1 0

x2 -1 0 -1 -1 0 0

x3 1 1 0 0 1 0

x4 1 1 0 0 0 0

x5 1 0 -1 0 0 1

x6 0 0 0 0 -1 0

Побудувати повний симетричний граф відстані між столицями (граф#5).

х1(

х6( (х2

х5( (х3

х4(

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

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

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

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

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

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

U1 = 756 U6 = 374 U11 = 1121

U2 = 536 U7 = 316 U12 = 194

U3 = 67 U8 = 326 U13 = 67

U4 = 842 U9 = 114 U14 = 628

U5 = 912 U10= 626 U15 = 526

Дані про відстані між столицями держав було взято з електронного
ресурсу – програми “3D World Map” і наведені в кілометрах. Допустимі
похибки в даних становлять не > 1000 m.

Для знаходження усіх маршрутів довжиною 4 ребра для графу #5 слід
зазначити, що, оскільки граф є повним і неорієнтованим, то всі маршрути
в ньому є подібні, змінюється лише вершина, а напрямок руху маршруту та
його вигляд залишається сталим, тому достатньо вказати усі можливі
маршрути, що виходять з однієї конкретної вершини, а усі інші маршрути
графу будуть аналогічні.

Маршрути довжиною 4 ребра, що виходять з вершини х1:

M1=(U8,U12,U13,U14), M2=(U8,U12,U4,U2), M3=(U8,U12,U9,U1),

M4=(U8,U12,U13,U10), M5=(U8,U12,U13,U5), M6=(U8,U12,U9,U15),

M7=(U8,U12,U9,U3), M8=(U8,U12,U13,U15), M9=(U8,U10,U15,U3),

M10=(U1,U2,U14,U13)….

І т. д… У даному графі можна побудувати дуже велику кількість маршрутів
довжиною 4 ребра.

Найдовший маршрут при неповторювані вершин буде мати такий вигляд (для
графу №5)

Ммах= (U1,U2,U14,U13,U12) – логічно, що довжина такого маршруту буде
мати не більше ніж 5 ланок.

Найдовший маршрут при неповторювані ребер буде мати довжину не більшу за
14 ланок, оскільки даний граф має непарні степені у кожній зі своїх
вершин, інакше граф був би ейлеревим і найдовший маршрут мав би довжину
15 ланок.

Ммах2=(U15,U10,U8,U9,U12,U11,U1,U3,U2,U4,U7,U14,U13).

Для не орієнтованого графу знайти цикли (граф #5).

C1 =(U8,U12,U13,U14,U2,U1);C2=(U8,U10,U13,U7,U3);C3=U9,U12,U10,U6,U2,U1)
;C4=(U15,U14,U7,U12,U8); C5=(U1,U4,U13,U10,U8)

Таких циклів у даному графі існує велика кількість. Це лише незначний
відсоток від усіх можливих.

Знайти гамільтонів та ейлерів цикли(граф #5).

Гамільтоновий цикл (проходить через усі вершини ): Мг =(U8, U12, U13,
U14, U2,U1).

Ейлерів цикл у даному графі побудувати неможливо, оскільки, граф не є
ейлеревим (степінь усіх вершин є непарною), отже ейлерів цикл для даного
графу не існує.

Знайти усі ланцюги та найдовший простий ланцюг(граф #5).

Найдовший простий ланцюг (не повторюються ні вершини, ні ребра ) графа
№5 буде таким Ммах=(U8,U12,U13,U14,U2)

Простий замкнений ланцюг для графа №5 має такий вигляд:
Мз=(U8,U12,U13,U14,U2,U1)

Деякі ланцюги в графі №5:

L1= (U8,U12,U13,U10,U6), L2= (U8,U10U13,U12,U6,U14), L3=
(U1,U2,U3U15,U8), L4= (U15,U13,U9

Похожие документы
Обсуждение
    Заказать реферат
    UkrReferat.com. Всі права захищені. 2000-2018