Розділ 4. Застосування теорії графів в інформаційній безпеці

Постановка задачі: спроектувати захищену комп’ютерну мережу, яка містить 14 комп’ютерів. Відстані між комп’ютерами вказані на графі. Необхідно визначити зв`язки цієї мережі. Зокрема:

- Виконати правильну нумерацію графу.

- Побудувати мінімальне дерево-остов.

- Визначити кількість шляхів від комп’ютера 1 до комп’ютера 14 та описати їх.

- Визначити та вказати найкоротші шляхи.

Темпи виробництва, його масштаби та спеціалізація окремих галузей, багатопрофільні зв’язки обумовлюють необхідність розробки ефективних методів планування та управління, які б давали можливість оцінити змінний стан системи та передбачити її майбутнє, щоб оптимізувати відповідний процес і керувати його перебігом. Системи об’єктів дослідження разом зі зв’язками між ними називаються мережею. Графічне зображення множини досліджуваних об'єктів і зв'язків між ними називається графом.

Граф доцільно зображати у вигляді діаграми. На діаграмі об'єкти зображаються пронумерованими точками або кружками, які називаються вершинами, зв'язки між об'єктами -відрізками ліній, які з'єднують відповідні об'єкти. Якщо зв'язок між двома об'єктами А та В однобічний (від А до В є зв'язок, а зворотний зв'язок відсутній), то це зображається орієнтованим відрізком, стрілка якого відповідає напрямку зв'язку. Такий однобічний орієнтований відрізок називається дугою, а графічне зображення неорієнтованих попарних зв'язків між об'єктами – ребрами (ситуація, коли об'єкт А може бути пов'язаний з об'єктом В і навпаки). Граф, вершини якого мають лише однобічний зв'язки, називається орієнтованим, або орграфом. Маємо такий граф комп’ютерної мережі з вказаними відстанями між вершинами (комп`ютерами). Виконаємо правильну нумерацію графа [12].

Рис. 4.1. Нумерація графа

Виконавши правильну нумерацію графа мережі, можна ефективно реалізувати алгоритм пошуку найкоротшого шляху між заданими вершинами. Реалізацію алгоритму приведено до побудови послідовності шляхів з однієї дуги, двох дуг, трьох дуг і т. д., які з’єднують вершини певного рангу з кінцевою вершиною. При цьому перегляд вершин виконується в послідовності зменшення їх номерів. На кожному етапі алгоритму відбувається перехід від вершини більш високого рангу до вершини меншого рангу за умови, що із множини всіх шляхів, які починаються в одній і тій же вершині, необхідно залишити для наступного кроку реалізації алгоритму лише найкоротший шлях від цієї вершини до завершальної. За правильної нумерації вершин такий упорядкований перехід у послідовності зменшення рангів відбувається автоматично, навіть за умови, коли нумерацію рангів вершин опущено.

Нумерацію виконаємо у довільному порядку, але від 1-ї вершини наступною по порядку буде та вершина, шлях до якої найкоротший і позначимо цю вершину 2, а всі інші нумеруємо довільно.

Рис. 4.2. Довільна нумерація вершин

При побудові графу планування захищеної мережі необхідно дотримуватися певних правил, щоб у подальшому можна було досліджувати його.

1. Граф планування захищеної мережі не повинен мати “глухих кутів”, тобто подій, з яких не виходить жодної роботи, окрім завершальної події. Поява “глухих кутів” подій свідчить про не досить ретельно виконаний аналіз взаємозв’язків.

2. На графові не може бути “хвостових” подій (окрім вихідної події), тобто подій, яким не передує жодна робота. Такою “хвостовою”подією є подія яка не може відбутися, отже, не можуть відбутися і наступні події.

3. Граф не може мати замкнутих контурів і петель, тобто шляхів, які з’єднують певні події з ними ж. Поява замкнутих контурів вимагає перегляду складу робіт та їх взаємозв’язків, після змістовного аналізу яких завжди з’являється можливість уникнути замкнутих контурів і петель.

4. На графові планування захищеної мережі повинна бути лише одна вихідна та лише одна завершальна подія [13].

Під час проектування залізниць,комп’ютерних мереж, ліній електропередач та інших ліній комунікації виникають проблеми побудови мережі з мінімальними витратами. Теоретично таке завдання успішно вирішується через побудову мінімального остовного дерева. Це завдання має низку методів рішення.

Інтерфейс програми має бути таким. Спочатку користувач вводить порядок графа, щоб програма могла сформувати таблицю введення даних (матриця терезів) з певним кількістю рядків і шпальт. Далі програма створює якийсь масивa[14] [14] (передбачається, що кількість вершин графа менше, або рівне 14). Цей масив ініціалізується: кожному a[i] [j] присвоюється 100 (передбачається, що максимальна довжина ребра менше 100). Потім дані з таблиці введення копіюються в масив. У осередку таблиці щось міститься у масив щось копіюється. Потім робиться цикл, який переривається тільки тоді, коли всі елементи масиву стануть знову рівні 100. Як працює цикл? Спочатку перебуває мінімальний елемент масиву (в галузі вище головною діагоналі матриці введення). Він запам'ятовується (змінна buf) і його присвоюється 100. Відповідно до алгоритму Прима, якщо ребро підходить мінімальний елемент викреслюється, а цикл починається з початку. Підходяще ребро чи ні? Складається масив з n елементів. Кожен елемент дорівнює 1 чи 0. Коли вершина входить у дерево, в елемент масиву з її номером записується 1 (спочатку всі елементи масиву, крім першого рівні 0). Щоб визначити підходяще ребро чи ні, треба подивитися, чи містяться одиниці в масиві (номери елементів рівні номерам вершин ребра). Якщо номерам вершин ребра відповідають обидві одиниця, отже, ребро не підходить. Якщо це основна умова не виконується – ребро підходить. Алгоритм перестає працювати, коли всі вершини включені у новий граф.

Окремо можна назвати процедуру малювання графа. Програма створює двомірний масив координат вершин графа (>krug [2] [14]). Вершини розташовуються на окружності на рівній відстані друг від друга. Такий спосіб дуже зручний, бо не треба тривожитися, що ребра будуть нашаровуватися одне на інше.

Визначимо кількість можливих шляхів від комп’ютера 1 до комп’ютера 14 та опишемо їх.

Дата добавления: 2015-08-31