Способи задання графів

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

Перед тим як розглядати ці способи, уведемо наступне формальне означення (яке нами неформально вже застосовувалося вище).

Означення 3.22. Граф називається поміченим, якщо його вершини відрізняються одна від іншої деякими позначками, наприклад v₁, v₂,…, v_n.

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

1. Аналітичний спосіб задання графів. Для n,m-графа G_n,m=(V,E) з вершинами v₁,v₂,…,v_nÎV і ребрами e₁,e₂,…,e_mÎE задається функція відображення j: V²®E, наприклад, переліком пар e_i=(v_i,v_k), упорядкованих у випадку, якщо G_n,m – орграф. Цього достатньо для визначення всіх відношень суміжності та інцидентності у заданому графі.

2. Геометричний спосіб задання графів. Графи наочно зображаються за допомогою рисунків на площині, які називають діаграмами графів. Вершинам графа ставляться у відповідність точки площини. Точки, що відповідають суміжним вершинам, з’єднуються лінією (відрізком або кривою, в орграфі – зі стрілкою), яка графічно відображає ребро (дугу). Діаграми графів часто скорочено називають графами, якщо це не визиває непорозумінь.

На рисунку 3.1 зображені діаграми графів G₁ i G₂ з прикладу 3.1.Діаграмами рис. 3.1,а і 3.1,б задається граф G₁, який є поміченим, неорієнтованим, простим, незваженим. Як бачимо з порівняння діаграм на рис. 3.1,а і 3.1,б, діаграма графа змінює свій вигляд у залежності від розташування точок (вершин) на площині.

Діаграмою рис. 3.1,в задається орграф G₂ з прикладу 3.1, який є поміченим і простим.

Додатково до рис. 3.1 геометричне задання графів різних видів подано на рис. 3.2. Для більшої наочності діаграми графів на рис. 3.2 показані непоміченими. Безумовно, цими зразкми графів не охоплюється їх різноманіття. Надаємо читачеві можливість самостійно визначити види графів (за означеннями 3.3 –3.5, 3.11 –3.12, 3.16 –3.20), заданих діаграмами на цьому рисунку.

3. Списочний спосіб задання графів. Це спосіб задання графів списками суміжностей, інциденцій та ваг. Зручною формою подання цих списків є таблиці відношень. Розглянемо цей спосіб на наступному прикладі.

Ми не будемо окремо розглядати технологію списочного задання неорієнтованих та незважених графів, оскільки вона очевидна з прикладу 3.2. Лише помітимо, що для незважених графів в таблицях 3.1 і 3.2 відсутні рядки ваг, а якщо граф неорієнтований, то слід мати на увазі, що пари (v_i,v_k) є невпорядкованими.

Задання графа таблицями відношень (табличними списками) зручно для зберігання і обробки інформации про ваги ребер (дуг) і вершин, пошуку вершин, інцидентних ребрам (дугам), пошуку суміжних вершин.

4. Матричний спосіб задання графів. Матричний опис графа зручний для обчислення числових характеристик графа і виконання різних алгебраічних операцій, оскільки спирається на глибоко розроблену теорію матриць.

Для задання графа за допомогою матриць потрібно всі його вершини занумерувати натуральними числами від 1 до n, а всі ребра (дуги) - числами від 1 до m. Саме так ми робили вище, тобто елементами графа G_n,m=(V,E) є вершини v_i, i=1,…, n і ребра (дуги) e_i, i=1,…, m.

Основними видами матриць, якими описуються графи, є матриці суміжностей, інциденцій та ваг.

Матриця суміжностей A графа (орграфа) G_n,m=(V,E) без петель являє собою квадратну n´n-матрицю, в якій елемент a_ij i-го рядка і j-го стовця дорівнює 1, якщо вершини v_i та v_j, i¹j суміжні, і дорівнює 0 при i=j. В матриці суміжностей мультиграфа елемент a_ij, i¹j дорівнює кількості ребер (дуг), що з'єднують вершини v_i та v_j.

Щоб скласти матрицю інцидентностей змішаного графа, слід замінити його еквівалентним орграфом. Для цього неорієнтоване ребро змішаного графа заміняється двома контрпаралельними дугами.

Матриця ваг. Матрицами ваг зазначають ваги ребер (дуг) графів (орграфів). Для простого графа (орграфа) матрицю ваг ребер (дуг) можна скласти такою ж за структурою, як матриця суміжностей. Елементи c_ij матриці ваг С визначаються таким чином: c_ij = p(e_l), тобто елемент c_ij на перетині i-го рядка та j-го стовпця матриці дорівнює вазі p(e_l) ребра (дуги), що з’єднує суміжні вершини v_i та v_j, i¹j; c_ii = 0; c_ij =0 або c_ij = ¥, якщо вершини v_i та v_j, i¹j не суміжні. Вибір значення 0 або ¥ елемента c_ij в останньому випадку залежить від практичного сенсу ваг ребер (дуг). Наприклад, якщо під вагою розуміється відстань між пунктами (вершинами) v_i та v_j на мавпі доріг, то у випадку їх несуміжності слід прийняти c_ij = ¥, а якщо під вагою розуміється пропускна здатність трубопроводу, то для несуміжних v_i та v_j слід прийняти c_ij =0.

Незалежно від того, простий граф (орграф) чи ні, матрицю ваг ребер (дуг) можна скласти за структурою матриці інциденцій, в який одиниці заміняються значеннями ваг відповідних ребер (дуг).