Поняття графу

Граф – двійка G = (X, U), де X - множина елементів (вершин, вузлів), а U - бінарне відношення на множині X (U X x X). Якщо |Х| = n, то граф є скінченим. Елементи U називають або дугами, або ребрами.

Якщо (X_i, X_j) – впорядкована пара, то такий граф називається орієнтованим (орграфом) а елементи U називаються дугами.

Якщо (X_i, X_j) = (X_j, X_i) то граф – неорієнтований (неорграф), а елементи U називаються ребрами.

F: U → R – якщо задано таку функцію, то граф є зваженим, де R – множина дійсних чисел, тобто відображення дуги на число.

Загалом:Ø U ⊆ X x X.

Для орієнтованого графу кількість ребер, що входять у вузол, називається напівступенем вузла, кількість ребер, що виходять з вузла — напівступенем результату. Кількість вхідних та вихідних ребер може бути довільною, у тому числі і нульовою. Граф без ребер називається нуль-графом.

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

Компонентами орграфу є: дуга, шлях, контур.

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

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

Компонентами неорграфу є, відповідно: ребро, ланцюг, цикл.

Ланцюг – безперервна послідовність ребер між парою вершин неорієнтованого графу. Неорієнтований граф називають зв'язним, якщо будь-які дві його вершини можна з'єднати ланцюгом. Якщо ж граф - незв'язний, то його можна розбити на підграфи. Наприклад:

Слабка зв'язність – орграф замінюється неорієнтованим графом, який, у свою чергу, є зв'язним.

Однобічна зв'язність – це така зв'язність, коли між двома вершинами існує шлях в одну або в іншу сторону.

Сильна зв'язність – це зв'язність, коли між будь-якими двома вершинами існує шлях в одну й в іншу сторону.

Отже, багатозв'язна структура має такі властивості:

1) на кожен елемент (вузол, вершину) може бути довільна кількість посилань;

2) кожен елемент може мати зв'язок з будь-якою кількістю інших елементів;

3) кожна зв'язка (ребро, дута) може мати напрямок і вагу.

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

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

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

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

Цикломатичне (або циклічний ранг) число графу S=m-n+c, де n – кількість вершин, m – кількість ребер, с – кількість компонент зв'язності графу.

Коциклічний ранґ (або коранґ) S*=n-c.

Неограф G є лісом тоді і тільки тоді, коли S(G)=0.

Неограф G має єдиний цикл тоді і тільки тоді, коли S(G)=1.

Контур неографу має S* ребер.

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

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

2 Подання графу в пам'яті комп'ютера

Графічний спосіб подання (якщо граф невеликий).

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

Одним із матричних способів подання графу є матриця суміжності. Нехай задано граф G = (X, U), |Х| = n. Маємо матрицю А розмірності n х n, що називається матрицею суміжності, якщо елементи її визначаються так:

Приклад 7.1. Нехай маємо граф, поданий рисунку 9.

Рисунок 9 – Приклад графу.

Йому відповідає така матриця суміжності:

	A	B	C	D	E
A
B
C
D
E

Розглянемо застосування матричної алгебри для визначення характеристик графу. Вираз a_ikLa_kj означає, що між вузлами i і j є дві дуги, що проходять через вузол k, якщо значення виразу дорівнює True.

Вираз означає, що завжди є шлях між цими вузлами довжиною 2, якщо вираз є істинним.

A L A = А⁽²⁾ – логічні операції заміняються арифметичними. Тоді кожний елемент а_ij буде подавати інформацію про те, чи є шлях з i в j (i,j = 1, 2,...,n)...

Вираз А⁽ⁿ⁾ = А^(n-1) L А означає, чи є шлях довжиною n між різними вузлами і. По діагоналі буде характеристика, чи є цикли (контури) у матриці.

– матриця зв'язності. Визначає, чи існує якийнебудь шлях між вузлами i та j.

Алгоритм обчислення заданого виразу:

1) Р = А;

2) повторити 3, 4 (k=1, 2,...,n);

3) повторити 4 для i=1,2,...,n;

4) повторити Р_іj = Р_іj ∨ (Р_іk L P_kj), j=1, 2,...,n...

У зв'язній пам'яті найчастіше подання графу здійснюється за допомогою структур суміжності. Для кожної вершини множини X задається множина М(Х_i) відповідно до дуг її послідовників (якщо це орграф) або сусідів (для неорграфу). Отже, структура суміжності графу G буде списком таких множин: <М(Х₁),М(Х₂),...,М(Х_n)> для всіх його вершин.

Приклад 7.2. Нехай маємо граф, поданий на рисунку 10 (вузли позначаємо у вигляді цифр: 1,2,..., n):

Рисунок 10 – Подання графу.

Для неорграфу:

1:2, 3;

2:1, 3;

3:1, 2;

4:5;

5:4.

Для орграфу:

1:2;

2:3;

3:1;

4:5;

5:-.

Структуру суміжності можна реалізувати масивом з т лінійно зв'язаних списків:

Подання графу може вплинути на ефективність алгоритму. Часто запис алгоритмів на графах задається в термінах вершин і дуг, незалежно від подання графу. Наприклад, алгоритм визначення кількості послідовників вершин: С(Х)=0, S – кількість дуг.

S = 0;

виконати:

початок

С(х)=0;

виконати: С(х) = С(х) + 1;

S = S + С(х);

кінець;

Контрольні питання

1. Дайте визначення графу.

2. Дайте визначення дерева за допомогою графу.

3. Поясніть призначення та принципи роботи алгоритмів проходження по графу.

4. Наведіть типи графів та порівняйте їх.

5. Назвіть структури даних, що використовуються в алгоритмах проходження вглиб та вшир.

Тести для закріплення матеріалу

1. Назвати компоненти неорграфу:

а) дуги;

б) ребра;

в) шлях;

г) контур;

д) ланцюг;

є) цикл.

2. Назвати компоненти орграфу:

а) дуги;

б) ребра;

в) шлях;

г) контур;

д) ланцюг;

є) цикл.

3. За визначенням знайти термін: орграф заміняється неорієнтованим графом, що у свою чергу є зв'язним:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

4. За визначенням знайти термін: між двома вершинами існує шлях в одну або в іншу сторону:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

5. За визначенням знайти термін: між будь-якими двома вершинами

існує шлях в одну й в іншу сторону:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

6. Способи подання графу:

а) графічний;

б) матричний;

в) описовий;

г) перелічуваний.

7. Знайти правильний вислів:

а) будь-яке дерево є графом;

б) будь-який граф є деревом;

в) будь-яке двійкове дерево є графом;

г) для того, щоб граф був деревом, в ньому не має бути циклів.

ЛЕКЦІЯ № 5

Тема: Алгоритми проходження графу

Ціль: розглянути алгоритми проходження графів та їх застосування

План