ШЛЯХИ І ЗВ’ЯЗНІСТЬ У ГРАФАХ
ОСНОВНІ ПОНЯТТЯ
Графи - це математична модель, за допомогою якої можна представляти та досліджувати формальний опис систем та процесів, що складаються з кінцевого числа фрагментів або компонентів, пов'язаних між собою певними залежностями.
При цьому природа залежностей компонентів систем може бути довільною для конкретних систем у різних галузях діяльності.
Наведемо приклади систем, вивчення та практичне використання яких пов'язане з поданням у формі кінцевого числа компонентів та зв'язків між ними.
1.Транспортні мережі. Компонентами таких систем є окремі населені пункти чи будівлі, а зв'язками – вказівка на наявність доріг, що їх з'єднують.
2. Молекули хімічних сполук. Частинами таких систем є окремі атоми, що становлять молекули, а зв'язками – хімічні сполуки між атомами.
3. Електронні схеми. Як компоненти, в них входять функціональні вузли або елементи, а зв'язки вказують на наявність проводів, що з'єднують вузли один з одним.
4. Адміністративний апарат установи. Тут частинами є окремі посадові особи, а зв'язки свідчить про наявність посадової підпорядкованості між співробітниками установи.
Природна форма наочного завдання систем, представлених графами, полягає у зображенні їх у площині чи тривимірному просторі те щоб частини систем були замкнутими областями простору, а зв'язку - дугами. При цьому, якщо для зв'язку між частинами системи характерна наявність спрямованості від однієї частини до іншої, то відповідна дуга забезпечується вказівкою відповідного напрямку.
Додатково потрібно, щоб вибрані області, що представляють частини графа, не мали спільних точок, а дуги,відбивають зв'язку, не перетиналися і містили всередині точок областей, відповідних частинам системи.
Зображення системи, на яку виконані перелічені умови, називається геометричної реалізацією цієї системи.
Приклад. Можлива наступна система підпорядкованості по службі співробітників апарату управління деякої фірми (рис.5.1.):
Головний Начальник Референт
менеджер відділу з правових
Рис. 5.1.
ВИЗНАЧЕННЯ І СПОСОБИ ЗАВДАННЯ ГРАФІВ
ВИЗНАЧЕННЯ
Графом називається всяка параG = (V,U ), в якійV - це кінцева множина, звана безліччю вершин графа, аU - кінцева множина ребер графа.
Будь-яке ребро графа представляється або однією парою вершин (а,b ), або двома протилежними парами (a,b ) і (b,a ). Якщо ребро зU представляється тільки однією парою (a,b ), воно називається орієнтованим ребром, що веде зa вb. У цьомуa називається початком, аb -кінцем такого ребра.
Якщо реброu представляється двома парами (a,b ) і (b,a ), тоu називається неорієнтованим ребром. Будь-яке неорієнтоване ребро між вершинамиa іb веде як зa доb, і назад. У цьому вершиниa іb є як початками, і кінцями цього ребра. Кажуть, що ребро веде як зa доb, так і зb доa.
Будь-які дві вершини, які з'єднуються рубом, називаються суміжними.
Розглянемо тільки такі графи, у яких всі ребра різні і не допускається одночасний зв'язок однієї і тієї ж пари вершин орієнтованим і неорієнтованим ребром абопарою протилежно орієнтованих ребер. Графи, які допускають можливість кількох ребер, що з'єднують пари вершин, називають мультиграфами. Такі графи у цьому навчальному посібнику не розглядаються.
(В останньому випадку відповідна пара ребер розглядатиметься як одне неорієнтоване ребро.)
Тоді ребра графів можна представляти просто парами вершин виду (a,b ), для яких додатково вказується; чи є ребро орієнтованим чи ні. У цьому випадку число ребер графа збігається з числом пар вершин, які є ребрами графа.
Тому надалі вважатимемо, щоU - це безліч пар вершин. При цьому кожне ребро є однією парою вершин або двома парами. Тобто, якщоG = (V,U ) і пара (a,b ) ребро графаG, то допустимий запис (a,b ) ÎU.
Зауваження. Можна вважати, що ці умови забороняють будь-яке дублювання ребер. Введені обмеження не призводять до обмеженості проведеного нижче вивчення графів, визначення та результати якого можуть бути перенесені або узагальнені на випадок графів, які мають довільну кількість ребер між парами вершин. При поданні графів з кратними ребрами вважатимуться, будь-яка пара вершин у яких з'єднана лише однією ребром, якому зіставлена числова характеристика, рівна кратності ребер між парами вершин. Така характеристика ребер виявляється корисною у випадках, коли ребрами зв'язку, що надаються, відносяться до різних класів або забезпечені додатковою інформацією про довжину, вартість або пропускну здатність.
Ребро, у якого вершини початку та кінця збігаються, називається петлею.
Число ребер, що виходять з певної вершиниa і відмінних від петель, називається ступенем цієї вершини і позначається якd (a ). Вершина a для якої виконано рівністьd (a ) = 0 називається ізольованою.
Граф, усі ребра якого неорієнтовані, називається неорієнтованим графом.
Як зазначалося, найпростішим способом представлення графів є їх геометрична реалізація. При цьому вершини графів зазвичай є точками простору, які позначені позначеннями вершин.
Розглянемо приклад геометричного завдання графа, який наведено на рис.5.2.:
a
v
e
C d
Мал.5.2.
Графи можна зображати так, щоб дуги, що відповідають ребрам, перетиналися. Таке уявлення графів не є геометричною реалізацією, але в деяких випадках може виявитися корисним або кращим.
Крім наочного геометричного зображення та подання графів використовуються й інші способи завдання. Вони дозволяють представляти графи у вигляді структур, які можна зберігати та обробляти за допомогою спеціальних алгоритмів та програм.
Розглянемо основні методи завдань графів з допомогою особливих структур.
1.Списки ребер
Подання довільного графа за допомогою списку ребер полягає у заповненні масиву, що містить усі пари вершин, які ребра представляють граф. Недоліком такого способу подання є можливість втрати інформації про ізольовані вершини.
Матриці суміжності
НехайG = (V,U ) - це граф із вершинамиV = v1, .v n>. Тоді матрицею суміжності цього графа називається квадратна таблиця розміромn n, рядки і стовпці якої поставлені ввзаємно однозначна відповідність вершин множиниV.
Значення елемента цієї матриці, розташованого на перетиніi -го рядка іj -го стовпця визначається за правилом:
=
Для графа, зображеного на рис.5.2., матриця суміжності має такий вигляд: