Способи збереження інформації о графах

• Матриця інцидентности A. По вертикалі указуються вершини, по горизонталі – ребра: a_ij=1 якщо вершина i інцидентна ребру j, 0 у противному випадку.

• Для орграфа a_ij=-1 якщо з вершини i виходить ребро j, a_ij=1 якщо у вершину i входить ребро j. Якщо ребро - петля, то a_ij=2.

• Список ребер. У першому стовпці ребра, у другому вершини їм інцидентні.

• Матриця суміжності - квадратна симетрична матриця. По горизонталі і вертикалі - усі вершини. D_ij= число ребер, що з'єднує вершини i,j.

• Матриця Кирхгофа: b_ij=-1, якщо вершини i і j суміжні, b_ij=0 якщо вершини i і j не суміжні, b_ii=-deg(i). Сума елементів у кожнім рядку і кожнім стовпці матриці Кирхгофа дорівнює 0.

Дерева і ліс

• Дерево - зв'язний граф без циклів.

• Ліс (чи ациклічний граф) - неограф без циклів (може бути і незв'язним).

• Теорема. Для неографа G з n вершинами без петель наступні умови еквівалентні:

1. G - дерево;

2. G - зв'язний граф, що містить n-1 ребро;

3. G - ациклічний граф, що містить n-1 ребро;

4. Будь-які дві незбіжні вершини графа G з'єднує єдиний ланцюг.

5. G - ациклічний граф, такий, що якщо в нього додати одне ребро, то в ньому з'явиться рівно один цикл.

Остов (каркас) зв'язного графа - дерево, що містить усі вершини графа.

Редукція графа - остов з найбільшим числом ребер.

Цикломатичне число графа к=m-n+c, де n - число вершин, m - число ребер, c - число компонентів зв’язності графа.

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

Ребра графа, що не входять у остов, називаються хордами.

• Цикл, що виходить при додаванні до остова графа його хорди, називається фундаментальним щодо цієї хорди.

• Число вершинної зв’язності G – найменше число вершин, видалення яких призводить до незв'язного чи одновершинного графа.

• Число реберної зв’язності G – найменше число ребер, видалення яких призводить до незв'язного чи одновершинного графа.

Планарність

• Плоский граф - граф з вершинами, розташованими на площині і непересічними ребрами.

• Планарний граф ізоморфний плоскому.

• Усякий подграф планарного графа планарний.

• Усякий плоский граф має одну, і лише єдину, необмежену грань. Ця грань є зовнішньою гранню графа, інші - внутрішні.

Теорема Эйлера. Для всякого зв'язного плоского графа n-m+f=2, де n - число вершин, m - число ребер, f - число граней.

Представлення графа у ЕОМ.

  Оскільки визначення графа включає дві множини - вершин і дуг, опис графа обов'язково включає ці два об'єкти. Інформаційні структури, що відповідають вершинам і дугам мережі, найчастіше мають послідовне представлення (файл, вектор), тому і нумерація вершин і дуг переважніше послідовна. Надалі будемо вважати, що вершини графа занумеровані цілими числами з діапазону 1:m, а дуги 1:n, що знімає проблему представлення цих об'єктів.

При відображенні Г: E --> V * V, що зіставляє кожній дузі e з E пари вершин (v,w) - початок і кінець дуги, виникає багато різних варіантів. При виборі варто орієнтуватися на ті задачі, для яких створюється структура. Найчастіше при роботі з графами приходиться відслідковувати відношення суміжності, тобто знаходити Г(v,-) - множину кінців дуг з початком в v і Г(v,+) - множину початків дуг з кінцем у v, а також відповідні множини дуг Е(v,-) і E(v,+) чи лінії на графі: ланцюга, шляхи, обходи.

Теоретично зручно розглядати матрицю суміжності графа:

R[ V,V ]: R[ і,j ] = числу дуг з і в j.

 Ця матриця визначає суміжність вершин графа, але має два основних недоліки:

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

2) Інформація матриці не дозволяє відновити номер дуги, що реалізує зв'язок між вершинами.

Другого недоліку позбавлена матриця інцидентності

{ 1, якщо e = ( w,v )

A[ V,E ]: A[ v,e ]={ -1, якщо e = ( v,w )

{ 0, інакше

Однак вона також заповнена рідко і не допускає петель у графі. Кожен стовбець матриці інцидентності містить рівно два ненульових елементи, 1 та –1.

Введемо пари векторів Left [ E ] і Right[ E ]. Запишемо в компонентах Left [ e ] = v та Right[e] = w для дуги e з E , e = ( v,w ). Тим самим цілком визначене відображення Т. Отримане представлення називається списком початків і кінців дуг.  Щоб однаково легко оперувати цими векторами, варто відсортувати множину дуг по початках і по кінцях, створюючи два індексних масиви покажчиків.

Проблема виникає, якщо граф неорієнтований, чи в ньому присутні неорієнтовані дуги. Справа в тому, що з алгоритмічної точки зору пара кінців дуги e = ( v,w ) обов'язково упорядкована і будь-яка спроба підвищити ефективність структури даних за рахунок сортування списку ускладнює облік їхньої несиметричності. Маються два виходи. Перший використовується коли не дуже багато неорієнтованих дуг - кожна з них заміняється парою орієнтованих протилежно. В другому наявність орієнтації дуги вказується у виді ознаки її параметра, скажемо, негативного значення довжини. Розшифровка ознаки повинна бути передбачена в алгоритмі, що використовує цю структуру.

Зв'язані структури також підходять для представлення довільного графа. Один зі способів тут - співвіднести кожній вершині v пари ланцюгових списків. Ці списки можуть мати різну довжину, але обійти це можна використовуючи записи зв'язку з покажчиками на наступний елемент списку (якщо він є).

Представлення дерева залежить від виду і числа вершин m дерева, від необхідних в алгоритмі операцій, від необхідності яким-небудь образом динамічно змінювати його. Найчастіше робота з деревом зводиться до якого-небудь його обходу, чи пошуку шляху.   Для того, щоб одержати ефективні структури даних, дерево вважають кореневим ієрархічним, навіть якщо це не так. Для дуг, напрямок яких не відповідає такій орієнтації, уводиться булевська ознака напрямку /наприклад - знак мінус перед позитивним числовим параметром дуги/. Дійсно, у кореневому ієрархічному дереві Г(v,+) порожньо для v = v0 і містить тільки один елемент (предка вершини) для інших вершин V. Завдяки цьому нумерація і параметри дуг дерева однозначно зв'язані з нумерацією його вершин. Таким чином, способи опису дерева:

1. Нумерація вершин - діапазон 1 : m , дуг 2 : m. Дуга з номером і = 2  m зв'язує вершину і та вершину next[і]. Якщо потрібно, задається логічна перемінна dir[i], значення якої визначає напрямок (i,next[i]) чи (next[i],i) . Представлення даних зручно, якщо потрібно знаходити ланцюг від довільної вершини до кореневої, номер якої 1. Якщо при цьому для кожного i виконується нерівність i >= next[i], то цикл FOR i:=1 TO m DO здійснює перегляд усіх вершин дерева зверху, тобто починаючи від кореневої.

2. Протилежний підхід виникає, якщо в ієрархічному дереві фіксувати Г(v,-) для кожної вершини v. Відзначимо, що ці множини утворять розбивку множини V без v0. Для опису цієї розбивки можна використовувати наступні варіанти. 1) Множини Г(1,-) Г(2,-) ,..., Г(м,-) записуються підряд у вектор RIGHT довжини m-1, для поділу підмножин можна використовувати вектор LEFT довжини m+1, вершини Г(v,-) знаходяться в записах RIGHT [LEFT [v-1]+1: LEFT[v]] (послідовний запис підмножин Г(v,-)). На жаль, це представлення даних вимагає багато пам'яті.

2) Роздільники містяться в тім же масиві, що й елементи Г(v,-), але відрізняються від них діапазоном значень чи знаком. Цей варіант може бути більш економним по пам'яті, але зручний лише в тому випадку, коли потрібний послідовний перегляд усіх вершин і множин Г(v,-).

3) Розбивку множин вершин можна реалізувати зв'язаними списками (наприклад, посиланнями масиву KONTUR). Нащадки однієї вершини (сини одного батька) при цьому складають круговий ланцюговий список. Потрібно ще одне посилання - від предка до якого-небудь з нащадків, якщо нащадків немає, воно порожнє. У сполученні зі списком NEXT ця структура дозволяє дуже ефективно працювати з будь-якою частиною дерева, знаходити шляхи, переглядати в заданому порядку вершини і навіть відслідковувати зміну дерева послідовною заміною його дуг.

3. Крім правильної нумерації в комбінаторних задачах використовуються й інші способи нумерації вершин графа. Так при підрахунку числа різних дерев з n позначеними вершинами використовується наступна процедура:

- Серед висячих вершин дерева знаходиться вершина v з найменшим номером.

- У список заноситься номер вершини, суміжної з v.

- Вершина v і інцидентна їй дуга видаляються з дерева і процес повторюється поки не залишиться дві останніх вершини.

Отриманий список з m-2 чисел з діапазону 1:m взаємно однозначно відповідає одному з можливих дерев.

Представлення бінарного дерева.

 Найбільш просте представлення бінарного дерева. Для цього досить завести для кожної вершини запис із двома покажчиками - умовно на лівого і правого нащадків вершини. Хоча m+2 покажчиків будуть порожніми, але іноді їх можна використовувати для інших даних (таких як числові параметри висячих вершин дерева). Якщо дерево збалансоване (рівень висячих вершин розрізняється не більш, ніж на 1) і правильно занумероване, то опис його обходу від кореневої вершини - просто числовий масив NEXT[1:m]. Вважається, що вершина і при цьому має нащадків NEXT[2*і] і Next[2*і+1], якщо 2*і і 2*і+1 не перевершують m. Цей спосіб представлення дерева використовується при сортуванні.