double arrow

Представлення графів у пам'яті ЕОМ

Перший вид представлення графів - за допомогою матриці суміжності - є найбільш зручним для простих графів, що містять невелику кількість ребер (дуг). Матриця суміжності є булевою, тобто містить “0” і “1”, кожен рядок матриці є представленим у вигляді рядка біт.

Недоліком способу є велика порожнина матриці, непродуктивне використання пам'яті для графів з малою кількістю ребер, а також великий час обробки матриці - приходиться обробляти як “1”, так і “0” - елементи.

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

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

Визначення. Список суміжності для вершини xiÎX, графу
G = <Х, Г> є список вершин з множини Г(xi), тобто це список кінців дуг, що виходять з вершини, чи список суміжних з xi вершин у випадку неорієнтованого графу.

Граф представляється у вигляді множини списків суміжності по одному для кожної вершини xiÎX. Якщо число дуг у графі мало, то цей спосіб є ефективним. Іноді завдають список суміжності у вигляді списків вершин з множин Г-1(xi) для кожної вершини xiÎX.

Приклад. Нехай заданий простий орграф (рис. 17.8) і його списки (рис. 17.9,а). Одна комірка списку містить поле ідентифікатора і поле адреси (рис. 17.9,б).

Рис. 17.8. Простий орграф

Рис. 17.9. Списки суміжності

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

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

1. Що є ступенем вершини графу, напівступенем заходу і напівступенем виходу вершини орграфу?

2. Як визначається цикломатичне число?

3. Якій граф є p-хроматичним, біхроматичним?

4. Що є хроматичним числом графу?

5. Що є множиною внутрішньої стійкості, що є найбільш внутрішньо стійкою множиною?

6. Що є числом внутрішньої стійкості графу?

7. Що є множиною зовнішньої стійкості, що є найменшою зовнішньо стійкою множиною?

8. Що є числом зовнішньої стійкості графу?

9. Яка різниця між матрицями суміжності та інцидентності?

10. Що є списком суміжності?

11. Як задається зважений граф за допомогою списку суміжності?

12. Що за допомогою списку суміжності можна відзначати у зваженому графі, як це виконується?


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: