Наука і техніка створюють все нові технології, які поступово виростають у нові галузі промисловості і займають значне місце в нашому житті. А ми, тим часом, непомітно для себе, починаємо все більше і більше користуватися їхніми плодами. І у цьому швидкоплинному світі процеси спілкування, передавання та обміну інформацією є надзвичайно важливими.
Будемо розуміти під комунікаціями процес встановлення зв’язку між двома точками простору та передачі інформації між ними. Тобто, є інформаційна мережа, що складається з центрів зберігання і переробки інформації. Деякі пари центрів з’єднані каналами зв'язку. Обмін інформацією між будь-якими двома центрами здійснюється або безпосередньо каналом, що їх з’єднує, або через інші канали і центри. Мережа вважається справною, якщо кожна пара центрів спроможна обмінюватися інформацією. Відомо, що в інформаційній мережі кожен з центрів безпосередньо пов'язаний каналом з кожним іншим центром. Поставимо питання: яке найменше число каналів зв'язку треба зруйнувати, щоб мережа стала несправною?
Надалі використаємо геометричне уявлення графа. Вершини графа зобразимо у вигляді точок на площині. Якщо дві вершини утворюють ребро, то відповідну пару точок з'єднаємо лінією. Граф, у якого кожна пара вершин з'єднана ребром, називається повним графом. Повний граф із n вершинами позначається Kn. Граф називається зв’язним, якщо від будь-якої його вершини можна по ребрах перейти до будь-якої іншої. В іншому випадку граф незв’язний. Будемо говорити, що дві вершини графа належать одній компоненті, якщо від однієї з них до іншої можна перейти ребрами графа. Кожна компонента є зв’язним графом. [1].
Інформаційній мережі природно зіставити граф G: вершини графа відповідають центрам мережі, а ребра графа - канали зв'язку. Тоді справній мережі буде відповідати зв’язний граф. Зруйнувати мережу можна двома способами: або знищити кілька центрів зберігання і переробки інформації, або пошкодити кілька каналів зв'язку. Першому способу еквівалентне видалення деякої множини вершин графа разом з ребрами, що з них виходять; другому - видалення деякої множини ребер. У кожному із способів графи повинні бути незв'язними.
Нагадаємо, що число зв'язності χ(G) графа G називається найменше число вершин, видалення яких (разом з ребрами, що з них виходять) приводить до незв'язного або одновершинного графу. Числом реберної зв'язності λ(G) графа G називається найменше число ребер, видалення яких призводить до незв’язного графу. [2]. Для графа G, зображеного на рисунку, χ(G) = 2, λ(G) = 3.
Можна показати, що для будь-якого зв'язного графа виконується співвідношення:
χ(G) ≤ λ(G) ≤ δ(G)
де δ(G) - мінімальний із степенів вершин графа. Права нерівність є очевидною, так як видалення всіх ребер, що виходять з вершини мінімального степеня, призводить до незв’язного графу.
Так як в нашій інформаційній мережі кожна пара центрів з’єднана каналом зв'язку, то мережі відповідає повний граф Kn. Для цього графа χ(Kn) = n - 1, оскільки яку б кількість вершин ми не видалили, граф залишиться зв’язним. Тому потрібно видаляти вершини до тих пір, поки не залишиться одна вершина, тобто χ(Kn) = n - 1. Отже
n-1 = χ(Kn) ≤ λ(Kn) ≤ δ(Kn) = n-1.
Тоді λ(Kn) = n-1, і для того, щоб вивести мережу з ладу, потрібно зруйнувати (n-1) канал.
Аналогічно з попереднім, можна показати, що після знищення будь-якого каналу мережа не вийде з ладу у випадку, коли кожен центр інформаційної мережі з’єднаний каналами зв’язку з парним числом центрів.
Графи є одним із способів подання інформації у графічній формі. Зображувальні засоби графів вирізняються простотою “алфавіту”, що містить два основних елементи – вершини графа, що позначаються в основному кружками (хоча ними можуть бути фігури довільної геометричної форми: ромб, квадрат, прямокутник тощо), і ребра, що позначаються відрізками ліній.
Засоби комп'ютерної візуалізації графів забезпечують всі необхідні інструментальні засоби і методи зручної маніпуляції графами. Моделювання за допомогою графів реалізує одну із важливих потреб – потребу наочності. Рисунок графа виступає як посередник між реальною дійсністю і математичною моделлю. Використання рисунків графів нерозривно пов'язане з процесами абстрагування і деталізації, за допомогою яких відбувається відокремлення тих ознак об'єкта, що моделюється, і які потім відображатимуться в моделі. Графові моделі забезпечують зв'язок мислення з реальними ситуаціями, служать засобом отримання нового знання.
Список літератури:
1. Татт У. Теория графов / У. Татт. – М.: Мир, 1988. – 424 с.
Кристофидес Н. Теория графов. Алгоритмический поход / Н. Кристофидес. – М.: Мир, 1978. – 429 с.
inforum.in.ua@ukr.net