Читайте также:
|
2. Побудувати граф відношення «спільні кордони». Побудувати матрицю суміжності.
1) Франція – V1
2) Німеччина – V2
3) Польща – V3
4) Італія – V4
5) Австрія – V5
6) Іспанія – V6
7) Білорусія – V7
8) Україна – V8
V2
e4
e1 V3
V1 e 5
e2
e3
e6 V4
e7 e8
V8 V5
e9
V7
V6
Матриця суміжності
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | |
 V1
| ||||||||
| V2 | ||||||||
| V3 | ||||||||
| V4 | ||||||||
| V5 | ||||||||
| V6 | ||||||||
| V7 | ||||||||
| V8 |
3. Обрахувати могутність країн за формулою
P = Wa× Nb× M1-b
Результати:
1) Франція – 72
2) Німеччина – 88
3) Польща – 10
4) Італія – 49
5) Австрія – 2
6) Іспанія – 28
7) Білорусія – 0,9
8) Україна – 5
4. Побудувати орієнтований граф безпосередньої загрози (за критерієм могутності та відношення «спільні кордони»).
V2
e4
e1 V3
V1 e 5
e2
e3
e6 V4
e7 e8
V8 V5
e9
V7
V6
5. Побудувати для графів (2), (4) матриці інцидентності та знайти степінь кожної вершини.
Матриця інцидентності для графа (2):
Степінь вершин:
| e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 | |
| V1
| |||||||||
| V2 | |||||||||
| V3 | |||||||||
| V4 | |||||||||
| V5 | |||||||||
| V6 | |||||||||
| V7 | |||||||||
| V8 |
V1 – 3
V2 – 3
V3 – 3
V4 – 2
V5 – 2
V6 – 1
V7 – 2
V8 – 2
Матриця інцидентності для графа (4):
Степінь вершин:
| e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 | |
| V1 |  -1
| ||||||||
| V2 | |||||||||
| V3 | -1 | ||||||||
| V4 | -1 | ||||||||
| V5 | -1 | -1 | |||||||
| V6 | -1 | ||||||||
| V7 | -1 | -1 | |||||||
| V8 | -1 |
V1 – -1, +2
V2 – +3
V3 – -1,+2
V4 – -1,+1
V5 – -2
V6 – -1
V7 – -2
V8 – -1,+1
6. Побудувати повний зважений граф за критерієм відстані між столицями країн, використовуючи матрицю суміжності, проставити вагу кожного ребра.
V2 590 V3
1481 1601
1100 1849
1338 717
1127 2337 675 2875
V1 1437 V4
795
555 2338
1251
2366 1255
2399
1350
V8 1260 V5
559
2156 1938 2385
1226 3714
3425
V7 V6
7. Використовуючи повний неорієнтований граф, визначити маршрути
m = 4, m = 6, m = 7.
m=4
V2 V3
V1 V4
V8 V5
V7 V6
m=6
V2 V3
V1 V4
 |
V8 V5
V7 V6
m=7
V2 V3
V1 V4
|
V8 V5
V7 V6
8. Використовуючи зважений граф (7), знайти дерево мінімальної ваги за алгоритмом Краскала.
Початковий граф
V2 590 V3
1100
675
V1 1437 V4
795
555
1251
V8 1260 V5
559
V7 V6
Рішення
| Vi | V1 | V1 | V1 | V2 | V2 | V3 | V3 | V4 | V7 |
| Vj | V2 | V4 | V6 | V3 | V5 | V7 | V8 | V5 | V8 |
| P(ViVj) |
| Vi | V3 | V7 | V2 | V2 | V3 | V1 | V4 | V1 | V1 |
| Vj | V7 | V8 | V3 | V5 | V8 | V2 | V5 | V6 | V4 |
| P(ViVj) |
VI={V3,V7};
VII={V3,V7,V8};
VIII={ V3,V7,V8,V2};
VIV={ V3,V7,V8,V2,V5};
VV={ V3,V7,V8,V2,V5,V1};
VVI={ V3,V7,V8,V2,V5,V1,V4};
VVII={ V3,V7,V8,V2,V5,V1,V4,V6};
Мінімальне покривне дерево
V2 590 V3
1100
675
V1 V4
555
1251
 |
V8 1260 V5
559
V7 V6
9. Використовуючи зважений граф, знайти дерево максимальної ваги за алгоритмом Прима.
Початковий граф
V2 590 V3
1481 1601
1100 1849
1338 717
1127 2337 675 2875
V1 1437 V4
795
555 2338
1251
2366 1255
2399
1350
V8 1260 V5
559
2156 1938 2385
1226 3714
3425
V7 V6
Рішення
 V1
| V2 | V3 | V4 | V5 | V6 | V7 | V8 | |
| V1 | ||||||||
| V2 | ||||||||
| V3 | ||||||||
| V4 | ||||||||
| V5 | ||||||||
| V6 | ||||||||
| V7 | ||||||||
| V8 |
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | |
| S |  0
|   2366
| ||||||
| I | V1 | V | V1 | V1 | V1 | V1 | V1 | V1 |
| SI | 
|  3714
| 
| |||||
| SI | V1 | V8 | V1 | V8 | V8 | V8 | V1 | V1 |
| SII | 
| 
|  3425
|
| ||||
| III | V1 | V6 | V6 | V8 | V6 | V8 | V6 | V1 |
| SIII | 
|  2875
| 
|
|
| |||
| IIII | V1 | V6 | V6 | V7 | V6 | V8 | V6 | V1 |
| SIV | 
| 
|  2399
|
|
| 
| ||
| IIV | V1 | V6 | V6 | V7 | V6 | V8 | V6 | V1 |
| SV |
| 
| 
|  2385
| 
| 
|
| |
| IV | V1 | V6 | V6 | V7 | V6 | V8 | V6 | V1 |
| SVI | 
| 
| 
| 
|
|
| 
| |
| IVI | V1 | V6 | V6 | V7 | V6 | V8 | V6 | V1 |
V8
V1 V6
 |
V2
 |
V7
 |
V5 V3
 |
V4
Дерево максимальної ваги
Дата добавления: 2014-12-15; просмотров: 136 | Поможем написать вашу работу | Нарушение авторских прав |