WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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


Лабораторна робота
на тему:
Теорія графів. Формування графічних моделей.
Об'єкт модулювання: Європейська безпека за 2000 р.
?
1. Обрати 6 будь-яких країн Європи.
Мною було обрано такі країни:
1. Словаччина (х1)
2. Чехія (х2)
3. Австрія (х3)
4. Польща (х4)
5. Угорщина (х5)
6. Румунія (х6)
2. Побудувати граф-відношення спільні кордони.(граф #1)
х1"
х6" "х2
х5" "х3
х4"
3. Використовуючи формулу могутності описати кожну країну
де:
N - кількість населення (у млн. чоловік) (1)
G - кількість ВВП на душу населення (у млн. доларів) (2)
W - витрата на зброю(у млн. доларів) (3)
= 0,38, = 0,62, = 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
4. Використовуючи Р, побудувати повний симетричний граф (граф #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
5. Побудувати орграф загрози.(граф #3)
х1"
х6" "х2
х5" "х3
х4"
6. Побудувати орграф безпосередньої загрози.(граф #4)
х1"
х6" "х2
х5" "х3
х4"
7. Побудувати для усіх заданих вище графів (1-4) матриці інцидентності.
Граф #1
xu 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
xU 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
xU 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
8. Побудувати для усіх заданих вище графів матриці суміжності.
Граф #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
9. Побудувати повний симетричний граф відстані між столицями (граф#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.
10. Для знаходження усіх маршрутів довжиною 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).
11. Для не орієнтованого графу знайти цикли (граф #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)
Таких циклів у даному графі існує велика кількість. Це лише незначний відсоток від усіх можливих.
12. Знайти гамільтонів та ейлерів цикли(граф #5).
Гамільтоновий цикл (проходить через усі вершини ): Мг =(U8, U12, U13, U14, U2,U1).
Ейлерів цикл у даному графі побудувати неможливо, оскільки, граф не є ейлеревим (степінь усіх вершин є непарною), отже ейлерів цикл для даного графу не існує.
13. Знайти усі ланцюги та найдовший простий ланцюг(граф #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Література:
1. http://www.wgeo.ru/table.shtml?pd=75&vvp=europe - Показники ВВП
2. http://www.wgeo.ru/table.shtml?id=29&loc=europe - Показники ВВП
3. Щорічник CІПРІ.2000р. - Показники витрат на озброєння.
Loading...

 
 

Цікаве