Хоча існує багато різних типів графів залежно від кількості вершин, кількості ребер, взаємозв’язку та їх загальної структури, деякі з таких поширених типів графів такі:
1. Нульовий граф
А нульовий граф — граф, між вершинами якого немає ребер. Нульовий граф також називають порожнім графом.
приклад
Нуль-граф з n вершинами позначається Nn.
2. Тривіальний граф
А тривіальний граф це граф, який має лише одну вершину.
приклад
У наведеному вище графіку є лише одна вершина 'v' без жодного ребра. Отже, це тривіальний граф.
3. Простий графік
А простий графік є неорієнтованим графом з немає паралельних країв і відсутність петель .
Простий граф, який має n вершин, ступінь кожної вершини не перевищує n -1.приклад
У наведеному вище прикладі перший граф не є простим графом, оскільки він має два ребра між вершинами A і B, а також має петлю.
Другий граф є простим графом, оскільки він не містить жодної петлі та паралельних ребер.
4. Неорієнтований граф
Ан неорієнтований граф це граф, ребра якого дорівнюють не спрямований .
приклад
У наведеному вище графі немає орієнтованих ребер, тому це неорієнтований граф.
5. Орієнтований граф
А орієнтований граф це графік, на якому краї спрямовані стрілками.
Орієнтований граф також відомий як орграфи .
приклад
На наведеному вище графіку кожне ребро спрямоване стрілкою. Спрямоване ребро має стрілку від A до B, означає, що A пов’язане з B, але B не пов’язане з A.
6. Заповніть графік
Граф, у якому кожна пара вершин з’єднана рівно одним ребром, називається графом повний графік . Він містить усі можливі ребра.
Повний граф з n вершинами містить рівно nC2 ребер і представлений Kn.
приклад
У наведеному вище прикладі, оскільки кожна вершина в графі з’єднана з усіма іншими вершинами через точно одне ребро, отже, обидва графи є повними графами.
7. Зв'язний граф
А зв'язний граф це граф, у якому ми можемо переходити з будь-якої однієї вершини в будь-яку іншу вершину. У зв’язному графі принаймні одне ребро або шлях існує між кожною парою вершин.
приклад
У наведеному вище прикладі ми можемо переходити від будь-якої однієї вершини до будь-якої іншої вершини. Це означає, що існує принаймні один шлях між кожною парою вершин, отже, це зв’язний граф.
8. Роз’єднаний граф
А роз'єднаний граф це граф, у якому не існує жодного шляху між кожною парою вершин.
приклад
Наведений вище граф складається з двох незалежних компонентів, які не зв’язані. Оскільки неможливо перейти від вершин одного компонента до вершин інших компонентів, отже, це роз’єднаний граф.
9. Регулярний графік
А Звичайний графік це граф, у якого степінь усіх вершин однаковий.
Якщо степінь усіх вершин дорівнює k, то він називається k-регулярним графом.
приклад
У наведеному вище прикладі всі вершини мають ступінь 2. Тому вони називаються 2- Звичайний графік .
10. Циклічний графік
Граф з 'n' вершинами (де n>=3) і 'n' ребрами, що утворюють цикл 'n' з усіма його ребрами, відомий як цикловий графік .
Граф, який містить принаймні один цикл, називається a циклічний графік .
У цикловому графі ступінь кожної вершини дорівнює 2.
Цикловий граф, який має n вершин, позначається Cn.
багатопотоковість java
Приклад 1
У наведеному вище прикладі всі вершини мають ступінь 2. Тому всі вони є циклічними графами.
Приклад 2
Оскільки наведений вище граф містить два цикли, отже, це циклічний граф.
11. Ациклічний граф
Граф, який не містить жодного циклу, називається графом ациклічний граф .
приклад
Оскільки наведений вище граф не містить жодного циклу, отже, це ациклічний граф.
12. Дводольний граф
А дводольний граф це граф, у якому набір вершин може бути розділений на два набори так, що ребра проходять лише між наборами, а не всередині них.
Граф G (V, E) називається дводольним графом, якщо його множину вершин V(G) можна розкласти на дві непорожні непересічні підмножини V1(G) і V2(G) таким чином, що кожне ребро e ∈ E (G) має свій останній суглоб у V1(G) та іншу останню точку у V2(G).
Розбиття V = V1 ∪ V2 називається подвійним розбиттям G.
Приклад 1
Приклад 2
13. Повний дводольний граф
А повний дводольний граф є дводольним графом, у якому кожна вершина в першому наборі з’єднана з кожною вершиною в другому наборі рівно одним ребром.
Повний дводольний граф — це дводольний граф, який є повним.
Complete Bipartite graph = Bipartite graph + Complete graph
приклад
Наведений вище графік відомий як K4,3.
14. Зірковий графік
Зірчастий граф — це повний дводольний граф, у якому n-1 вершин мають ступінь 1, а одна вершина має ступінь (n -1). Це точно виглядає як зірка, де (n - 1) вершини з'єднані з однією центральною вершиною.
Зірчастий граф з n вершинами позначається Sп.
приклад
У наведеному вище прикладі з n вершин усі (n-1) вершини з’єднані з однією вершиною. Отже, це зірчастий графік.
15 Зважений графік
Зважений граф — це граф, ребра якого позначені деякими вагами або числами.
Довжина шляху у зваженому графі є сумою ваг усіх ребер шляху.
приклад
У наведеному вище графіку, якщо шлях a -> b -> c -> d -> e -> g, то довжина шляху дорівнює 5 + 4 + 5 + 6 + 5 = 25.
16. Мультиграф
Граф, у якому є кілька ребер між будь-якою парою вершин або є ребра від вершини до самої себе (петля), називається мульти - граф .
приклад
У наведеному вище графі множини вершин B і C з’єднані двома ребрами. Аналогічно, множини вершин E і F з'єднані трьома ребрами. Отже, це мультиграф.
17. Плоский граф
А плоский граф це граф, який ми можемо намалювати на площині таким чином, щоб жодні два його ребра не перетиналися одне з одним, за винятком вершини, з якою вони інцидентні.
приклад
Наведений вище графік може здатися не плоским, оскільки його ребра перетинаються. Але ми можемо перемалювати наведений вище графік.
Три плоскі малюнки наведеного вище графіка:
Наведені вище три графи не складаються з двох ребер, що перетинають одне одного, тому всі наведені вище графи є плоскими.
18. Неплоский граф
Граф, який не є плоским графом, називається неплоским графом. Іншими словами, граф, який не можна намалювати без принаймні пари його ребер, що перетинаються, відомий як неплоский граф.
приклад
Наведений вище графік є неплоским.