Теория графов

Тема : Теорія графів.

Індивідуальні завдання для самостійної роботи студентів:

Формування моделей на графах. Об’єкт моделювання міжнародна безпека.

1. Вибрати 9 країн світу.
2. Побудувати граф відношення «спільні кордони»
3. Обрахувати могутність країн за формулою:

                        P = Wα⋅ Nβ ⋅ Mγ 

де Р - могутність держави;

Wα  - внутрішній валовий продукт на душу населення;

Nβ   - кількість населення країни;

M1-α - витрати на озброєння.        ([pic 1])

Параметри  α і β лежать в межах від 0 до 1. Якщо α = 1 зростає ВВП, тобто держава миролюбна. Якщо α = 0, то M1 , отже могутність виражається витратами на оборону, тобто держава мілітаристська. Як правило показник

α = 0.5,     [pic 2]

1. Побудувати повний симетричний зважений граф

1. Побудувати повний орієнтований зважений граф за критерієм могутності кожної країни. Вага вершин - оцінка могутності країни.
2. Побудувати орієнтований граф безпосередньої загрози (за критерієм могутності та відношення «спільні кордони».
3. Побудувати для графів 1-4 матриці інцидентності.
4. Використовуючи матрицю інцидентності повного неорієнтованого графу побудувати матрицю перерізів та контурів.
5. Використовуючи повний неорієнтований граф визначити маршрути  

m = 4; m = 6; m = 7.

1.  Використовуючи повний неорієнтований граф визначити ейлеровий та гамільтоновий цикли.  
2. Побудувати повний зважений граф за критерієм відстані між столицями країн.
3. Використовуючи зважений граф знайти дерево мінимальної ваги за алгоритмом Краскала.
4.  Використовуючи зважений граф знайти дерево максимальної ваги за алгоритмом  Прима.
5. Використовуючи зважений граф знайти мінімальний та максимальний цикли  методом «гілок та границь».