Типи графів у структурі даних з прикладами

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

Графи можуть бути кількох типів залежно від положення вузлів і ребер. Ось кілька важливих типів графіків:

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

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

Ось приклад орієнтованого графа.

• Ми можемо перейти від вузла A до D.
• Однак ми не можемо переходити від вузла D до вузла A, оскільки край вказує від A до D.
• Оскільки граф не має вагових коефіцієнтів, подорож від вершини A до D коштуватиме так само, як подорож від D до F.

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

Неорієнтований граф містить ребра без вказівників. Це означає, що ми можемо подорожувати навпаки між двома вершинами.

Ось простий приклад неорієнтованого графа.

На наведеному вище графіку

• Ми можемо перейти від А до Б
• Ми також можемо перейти від B до A
• Ребра не містять напрямків.

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

Зважений графік

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

Ось приклад зваженого графіка (спрямованого).

• Від A до B є перевага, а вага дорівнює 5, що означає, що перехід від A до B коштуватиме нам 5.
• A вказує на B, але на цьому графіку B не має прямого краю над A. Отже, ми не можемо подорожувати від B до A.
• Однак, якщо ми хочемо перейти від A до F, існує кілька шляхів. Шляхи ADF, ABF. ADF коштуватиме (10+11) або 21.
• Тут шлях ABF буде коштувати (5+15) або 20. Тут ми додаємо вагу кожного ребра шляху.

Ось приклад неорієнтованого графа з вагами:

Тут край має вагу, але не має напрямку. Отже, це означає, що подорож від вершини A до D коштуватиме 10 і навпаки.

Двонаправлений графік

Двонаправлені та неорієнтовані графи мають спільну властивість. Тобто

• Як правило, неорієнтований граф може мати одне ребро між двома вершинами.

Наприклад:

• Тут перехід від A до D або D до A коштуватиме 10.
• У двонаправленому графі ми можемо мати два ребра між двома вершинами.

Ось приклад:

Подорож від A до D коштуватиме нам 17, але подорож від D до A коштуватиме нам 12. Отже, ми не можемо призначити дві різні ваги, якщо це неорієнтований граф.

Нескінченний графік

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

Ось приклад нескінченного графа:

Нульовий графік

Нульовий граф містить лише вузли або вершини, але без ребер. Якщо задано граф G = (V, E), де V — вершини, а E — ребра, він буде нульовим, якщо кількість ребер E дорівнює нулю.

Ось приклад нульового графіка:

Тривіальний граф

Структура даних графа вважається тривіальною, якщо є лише одна вершина або вузол без ребер.

Ось приклад тривіального графа:

Мультиграф

Граф називається мультиграфом, якщо між двома вершинами присутні кілька ребер або вершина має петлю. Термін «Петля» в структурі даних графа означає ребро, що вказує на той самий вузол або вершину. Мультиграф може бути спрямованим і неорієнтованим.

Ось приклад Multi Graph:

Є два ребра від B до A. Крім того, вершина E має автопетлю. Наведений вище графік є орієнтованим графом без ваг на ребрах.

Повний графік

Граф є повним, якщо кожна вершина має орієнтовані або неорієнтовані ребра з усіма іншими вершинами.

Припустимо, що є загальна кількість вершин V і кожна вершина має рівно V-1 ребра. Тоді цей графік буде називатися повним графіком. У цьому типі графа кожна вершина з’єднана з усіма іншими вершинами через ребра.

Ось приклад повного графа з п’ятьма вершинами:

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

Підключений граф

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

Ось приклад підключеного графіка:

Ось деяке пояснення наведеного вище «повного прикладу графіка».

• Якщо припустити, що між C і F немає ребра, ми не можемо подорожувати від A до G. Однак ребро C до F дозволяє нам подорожувати до будь-якого вузла з даного вузла.
• Повний граф є зв’язаним графом, оскільки ми можемо переходити від вузла до будь-якого іншого вузла в даному графіку.

Циклічний графік

Граф називається циклічним, якщо в ньому є один або більше циклів.

Ось приклад циклічного графіка:

Тут вершини A, B і C утворюють цикл.

Граф може мати кілька циклів усередині.

Спрямований ациклічний графік (DAG)

Граф називається спрямованим ациклічним графом або DAG, якщо всередині графа немає циклів. DAG важливий під час виконання Топологічне сортування або знайти наказ про виконання. DAG також важливий для створення систем планування або сканування залежностей ресурсів тощо. Однак наведений вище графік не містить жодного циклу.

Ось простий приклад спрямованого ациклічного графа (DAG):

Графік циклу

Циклічний графік – це не те саме, що циклічний графік. У Cycle Graph кожен вузол матиме рівно два з’єднані ребра, тобто кожен вузол матиме рівно два ступені.

Ось приклад циклічного графіка:

Дводольний граф

Ці види діаграми це спеціальні види графів, де вершини призначаються двом множинам.

Дводольний граф повинен відповідати правилу:

• Два набори вершин повинні бути різними, що означає, що всі вершини повинні бути розділені на дві групи або набори.
• Один і той самий набір Вершини не повинні утворювати жодних ребер.

Графік Ейлера

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

Ось приклад графіка Ейлера:

Усі вершини мають парні ступені. Вершини A, D, E і H мають два ступені. Тут вузол C має чотири ступені, що є парним.

Графік Гамільтона

Граф Гамільтона — це граф з’єднання, де ви можете відвідати всі вершини з заданої вершини, не відвідуючи той самий вузол або використовуючи те саме ребро. Цей тип зв’язаного графа відомий як «граф Гамільтона». Шлях, який ви відвідуєте, щоб перевірити, чи є даний графік графом Гамільтона, відомий як гамільтонів шлях.

Ось простий приклад графіка Гамільтона:

На цьому зображенні ми можемо відвідати всі вершини з будь-якого вузла на наведеному вище графіку. Одним із шляхів може бути ADCHBE. Також можна знайти цикл Гамільтона. Цикл Гамільтона починається і закінчується в одній вершині. Отже, цикл Гамільтона буде ADCHBEA.