Лабораторна робота
на тему:
Теорія графів. Формування графічних моделей.
Об’єкт модулювання: Європейська безпека за 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
Література: http://www.wgeo.ru/table.shtml?pd=75&vvp=europe - Показники ВВП HYPERLINK http://www.wgeo.ru/table.shtml?id=29&loc=europe http://www.wgeo.ru/table.shtml?id=29&loc=europe - Показники ВВП Щорічник CІПРІ.2000р. – Показники витрат на озброєння.
Нашли опечатку? Выделите и нажмите CTRL+Enter