Інцидентність та суміжність у графах, матриці суміжності, матриці інцидентності, списки інцидентності

Інцидентність вершин та ребер графа, суміжність вершин графа

Інцидентність - це коли вершина a є або початком або кінцем ребра e. Дві вершини називаються інцидентними, якщо вони мають спільне ребро.

Для того, щоб задати граф аналітично, множини V вершин графа та безлічі U ребер графа, які фігурували в визначення графа, буде недостатньо. Потрібно ще й безліч P трійок виду (a, u, b) , що вказують яку пару a, b елементів безлічі вершин V з'єднує той чи інший елемент u безлічі ребер U графа. Елементи множини P називаються інцидентами графа. Ось ми і підійшли до одного з перших понять теорії графів. інцидентності.

Поняття інцидентності - одне з головних під час створення структур даних уявлення графів у пам'яті ЕОМ, яких ми перейдемо після прикладу 1.

приклад 1. Задати аналітично граф, поданий на малюнку нижче. (Рис. А)

Рішення. Поширені помилки - не помітити вершини графа, які не з'єднані з жодною іншою вершиною, у тому числі із самою собою, і не включити їх у безліч вершин графа, а також вказати не всі ребра графа, що з'єднують дві вершини. Тому вершину f даного графа обов'язково включаємо в безліч вершин графа V , а, ребра 6 і 7, хоча вони з'єднують одну і ту ж вершину саму з собою і обидва не мають напрямку, включаємо в безліч ребер U .

Отже, задаємо граф такими множинами:

Сумежність вершин графа - це коли дві вершини графа з'єднані рубом.

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

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

Найчастіше використовуються три такі структури даних - матриця суміжності, матриця інцидентності і список інцидентності.

Матриці суміжності

Матриця суміжності, як і матриця інцидентності, дозволяє встановити безліч вершин, сусідніх із заданою (тобто розглядається у конкретній задачі), не вдаючись до повного перегляду всієї матриці. Матриці суміжності зазвичай є двовимірним масивом розміру n x n , де n - Число вершин графа.

Матриця суміжності S - це квадратна матриця, в якій і число рядків, і число стовпців дорівнює n - Чисельність вершин графа. У комірки матриці суміжності записуються деякі числа залежно від цього, з'єднані відповідні вершини ребрами чи ні, і зажадав від типу графа.

Матриця суміжності для неорієнтованого графа

Елемент матриці суміжності s ij неорієнтованого графа визначається так:

- дорівнює одиниці, якщо вершини v i та v j суміжні;

- дорівнює нулю, якщо вершини v i та v j не суміжні.

Якщо елемент матриці v ij має місце i = j , тобто елемент знаходиться на діагоналі, цей елемент дорівнює одиниці, якщо цей елемент має петлю, і нулю, якщо елемент не має петлі.

приклад 2. Скласти матрицю суміжності для графа, поданого на малюнку нижче.

Таким чином, матриця суміжності неорієнтованого графа симетрична щодо головної діагоналі.

Матриця суміжності для орієнтованого графа

Елемент матриці суміжності s ij орієнтованого графа визначається так:

- дорівнює одиниці, якщо з вершини v i у вершину v j входить дуга;

- дорівнює нулю, якщо з вершини v i у вершину v j дуга не входить.

Як для неорієнтованих графів, так і для орієнтованих, якщо для елемента матриці v ij має місце i = j , тобто елемент знаходиться на діагоналі, цей елемент дорівнює одиниці, якщо цей елемент має петлю, і нулю, якщо елемент не має петлі.

приклад 3. Скласти матрицю суміжності для графа, поданого на малюнку нижче.

Таким чином, матриця суміжності орієнтованого графа не симетрична.

Матриця суміжності для графа з кратними ребрами

Якщо у графі є вершини, з'єднані між собою кількома ребрами, то елемент матриці суміжності s ij дорівнює числу ребер, що з'єднують вершини v i та v j. З цього випливає, що якщо вершини v i та v j не з'єднані ребрами, то елемент матриці суміжності s ij дорівнює нулю.

приклад 4. Скласти матрицю суміжності для графа, поданого на малюнку нижче.

Матриця суміжності для виваженого графа

У разі виваженого графа елемент матриці суміжності s ij дорівнює числу wякщо існує ребро між вершинами v i та v j з вагою w. Елемент s ij дорівнює нулю, якщо ребер між вершинами v i та v j немає.

Приклад 5. Скласти матрицю суміжності для графа, поданого на малюнку нижче.

Матриці інцидентності

Матриця інцидентності H - це матриця розміру n x m , де n - Число вершин графа, m - Число ребер графа. Зазвичай у матриці інцидентності рядки відповідають вершинам графа, а стовпці – ребрам графа.

Матриця інцидентності для неорієнтованого графа

Елемент матриці інцидентності для неорієнтованого графа h ij визначається наступним чином:

- дорівнює одиниці, якщо вершина v i інцидентна ребру e j;

- дорівнює нулю, якщо вершина v i не інцидентна ребру e j.

Приклад 6. Скласти матрицю інцидентності для графа, поданого на малюнку нижче.

Матриця інцидентності для орієнтованого графа

Елемент матриці інцидентності для орієнтованого графа h ij визначається наступним чином:

- дорівнює мінус одиниці, якщо вершина v i є початком ребра e j;

- дорівнює одиниці, якщо вершина v i є кінцем ребра e j;

- дорівнює нулю, якщо вершина v i не інцидентна ребру e j.

Приклад 7. Скласти матрицю інцидентності для графа, поданого на малюнку нижче.

Списки інцидентності

Графи значного обсягу доцільно зберігати у пам'яті комп'ютера у формі списків інцидентності.

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

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

Приклад 8. Скласти списки інцидентності для графа, поданого на малюнку нижче.

Переваги та недоліки кожного способу

Матриці суміжності та інцидентності доцільніше використовувати коли:

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

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

Списки інцидентності доцільніше використовувати коли:

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

Насправді списки частіше використовують у прикладних цілях.

Матриця інцидентності.

Говорити про те, що ребро g і кожна з вершин u і y інцидентна gстоїть лише в тому випадку, якщо g з'єднує u і y. Усвідомивши це, перейдемо до розгляду цього методу. Матриця інцидентності будуватись за схожим, але не за тим же принципом, що і матриця суміжності. Так якщо остання має розмір n×n, де n - Число вершин, то матриця інцидентності - n×m, тут n - Число вершин графа, m - Число ребер. Тобто тепер, щоб задати значення будь-якої комірки, потрібно зіставити не вершину з вершиною, а вершину з ребром.

У кожному осередку матриці інцидентності неорієнтованого графа коштує 0 або 1, а у випадку орієнтованого графа, Вносяться 1, 0 або -1. Те саме, але найбільш структуровано:

1) Неорієнтований граф

a. 1 – вершина інцидентна ребру

b. 0 – вершина не інцидентна ребру

2) Орієнтований граф

a. 1 - вершина інцидентна ребру, і є його початком

b. 0 – вершина не інцидентна ребру

c. -1 – вершина інцидентна ребру, і його кінцем

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

Ребра позначені літерами від a до e, вершини – цифрами. Усі ребра графа не спрямовані, тому матриця інцидентності заповнена позитивними значеннями.

Для орграфа графа матриця має трохи інший вигляд. У кожну з її осередків внесено одне із трьох значень. Зверніть увагу, що нулі у цих двох матрицях (рис. 1 і 2) займають однакові позиції, адже в обох випадках структура графа одна. Але деякі позитивні одиниці змінилися на негативні, наприклад, у неорієнтованому графі осередок (1, b) містить 1, а в орграфі -1. Справді, це доречно, тобто. до. у першому випадку ребро b не спрямоване, тоді як у другому – спрямоване, і, причому вершиною входу йому є вершина «1».

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

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