Практичне завдання
Формування графових моделей – європейська безпека 2000
1. Країни Європи
Франція (х1),Австрія(х2),Португалія(х3),Іспанія(х4),Італія(х5).
Граф спільних кордонів:
№1
2. Могутність країн
Р=N G W
N- населення країни – 0,38
G- ВВП на душу населення – 0,62
W- витрати на озброєння – 0,28
Населення ВВП на душу населення($) Витрати на озброєнн (млн.$)
Могутність
Франція 59551,2 24223 46792 692353,294
Австрія 8150,8 26765 2131 145663,637
Португалія 10066,3 17290 2685 128418,575
Іспанія 40038 19472 8675 324406,469
Італія 57679,8 23626 23458 555101,527
За цим індексом бачимо, що наймогутнішими є Франція та Італія, які
потенційно загрожують безпеці інших країн. Найуразливішою є Португалія.
2.1. Повни симетричний зважений граф за критерієм могутності
3. Повний орієнтований граф загрози
№2
№3
4. Орієнтований граф безпосередньої загрози за критеріями могутності та
відношенням кордонів
№4
5. Матриці інцидентності та матриці суміжності для цих 4 графів:
№1
х1 х2 х3 х4 х5
х1 0 0 0 1 1
х2 0 0 0 0 1
х3 0 0 0 1 0
х4 1 0 1 0 0
х5 1 1 0 0 0
U1 U2 U3 U4
х1 1 1 0 0
х2 0 0 1 0
х3 0 0 0 1
х4 1 0 0 1
х5 0 1 1 0
№2
U1 U2 U3 U4 U5 U6 U7 U8 U9 U10
х1 1 1 1 1 0 0 0 0 0 0
х2 1 0 0 0 1 1 1 0 0 0
х3 0 1 0 0 0 0 1 1 1 0
х4 0 0 1 0 0 1 0 0 1 1
х5 0 0 0 1 1 0 0 1 0 1
х1 х2 х3 х4 х5
х1 0 1 1 1 1
х2 1 0 1 1 1
х3 1 1 0 1 1
х4 1 1 1 0 1
х5 1 1 1 1 0
№3
U1 U2 U3 U4 U5 U6 U7 U8 U9 U10
х1 1 1 1 1 0 0 0 0 0 0
х2 -1 0 0 0 -1 -1 1 0 0 0
х3 0 -1 0 0 0 0 -1 -1 -1 0
х4 0 0 -1 0 0 1 0 0 1 -1
х5 0 0 0 -1 1 0 0 1 0 1
х1 х2 х3 х4 х5
х1 0 1 1 1 1
х2 0 0 1 0 0
х3 0 0 0 0 0
х4 0 1 1 0 0
х5 0 1 1 1 0
№4
U1 U2 U3 U4
х1 1 1 0 0
х2 0 0 -1 0
х3 0 0 0 -1
х4 -1 0 0 1
х5 0 -1 1 0
х1 х2 х3 х4 х5
х1 0 0 0 1 1
х2 0 0 0 0 0
х3 0 0 0 0 0
х4 0 0 1 0 0
х5 0 1 0 0 0
6. Для повного симетричного графу проставимо вагу ребер відповідно до
відстані між столицями країн (км).
Париж(y1), Відень(y2), Лісабон(y3), Мадрид(y4), Рим(y5).
Y1 y2 y3 y4 Y5
Y1 – 1263 1802 1264 1433
Y2 1263 – 2996 2400 1145
Y3 1802 2996 – 645 2667
Y4 1264 2400 645 – 2022
Y5 1433 1145 2667 2022 –
P(U1)=1263
P(U6)=2400
P(U2)=1802
P(U7)=2996
P(U3)=1264
P(U8)=2667
P(U4)=1433
P(U9)=645
P(U5)=1145
P(U10)=2022
7. Для повного орієнтованого графу загрози ( №3) визначимо маршрути (
М=4)
Можливих маршрутів всього 1, він є максимальним.
М= U4,U5,U6,U9
8. Для неорієнтованого графа визначаємо прості цикли.
= U7, U5, U10, U9
9. Знайдемо Ейлерів цикл
У даному випадку цикл існує
= U5, U9, U2 U3 U6 U1 U4 U10 U9 U7
10. Знайдемо Гамільтоновий цикл
U = U1, U7, U9 U10 U4
11. Будуємо дерева графу
Відповідно до формул кількості можливих дерев графів, ми можемо
побудувати 125 дерев, ось декілька з них:
Нашли опечатку? Выделите и нажмите CTRL+Enter