Операції над графами (поняттями) Операція вилучення ребра
Операція вилучення вершини
а з E вилучені всі ребра, інцидентні з вершиною v.
Операція вилучення вершини (рис. 41) не залежить від порядку, в якому вилучаються вершини з графа
Операції вилучення ребра, вершини і перехід до підграфа - це операції, за допомогою яких можна з початкового графа одержати графи з меншим числом вершин і ребер.
Операція введення ребра
Операція введення вершини в ребро
Нехай (u, у) - деяке ребро графа G. Введенням вершини w в ребро (u, v) називається операція внаслідок якої одержимо два ребра (u, w) і (w, v), а ребро (u, v) при цьому вилучається з графа G.
Операція об’єднання графів
Операція диз’юнктивного об’єднання графів дає можливість ввести до розгляду ще один важливий тип графів.
Граф називається зв’язним, якщо його не можна подати у вигляді диз’юнктивного об’єднання двох підграфів, і незв’язним - у протилежному випадку.
Отже, всякий незв’язний граф можна зобразити у вигляді
диз’юнктивного об’єднання скінченого числа зв’язних підграфів. Кожний з таких зв’язних підграфів називається компонентом зв’язності.
Зв’язний регулярний граф степеня 2 називається циклічним графом (рис. 42). Циклічний граф з п вершинами позначається Cn.
Циклічний граф
Рис. 42
Добуток графів
Добутком графів G = (V, Е) і H = (Vb Ei) (рис.
43), називається граф F = G * Н, у якого V = V * Vb a E визначається таким чином: вершини (u, ні) і (v, Vi) суміжні в F тоді і лише тоді, коли u = V, a Ui і Vi суміжні в H або Ui = vb a u і v суміжні в G.
Рис. 43
Ототожнення (злиття) вершин
Якщо G = (V, Е) - граф, u, v - дві його вершини і Cm(u) = {ub...Uk}, Cm(v) = {vb... Vi}, то граф H = G - u - v, одержаний приєднанням нової вершини u∣ до множини вершин H і множини ребер (ul, щ), (ul, Vj) (і = 1, 2,...k, j = 1, 2,... 1) до множини ребер Н, називається графом, одержаним із G ототожненням вершин u і v.
Операція стягування ребра
Операція стягування ребра (u, v) в графі G = (V, Е) (рис. 44), означає ототожнення вершин u і v в графі G. Операція стягування ребра дає змогу ввести таке поняття. Граф G називається графом, який стягується до графа Н, якщо H можна одержати з G за допомогою деякої послідовності операцій стягування ребра, легко помітити, наприклад, що граф Петерсена стягується до графа K5 де п < 5. Очевидно також що всякий непустий зв’язний граф стягується до Кз. Наприклад, простий ланцюг Pn не стягується до Кз. Логічно ввести параметр λ(G) - максимум порядків повних графів, до яких стягується граф G. Параметр λ(G) називається числом Хадвігера графа G.
Операція роздвоєння (розщеплення) вершин
Нехай V - деяка з вершин графа G. Розіб’ємо множину суміжних з нею вершин на дві частини M і Р, а потім виконаємо таке перетворення графа G: вилучимо вершину v разом з інцидентними їй ребрами і введемо дві нові вершини, вершини u і w разом з ребром, яке з’єднає ці вершини, вершину u з’єднаємо ребром з кожною вершиною множини М, а вершину w - з кожною вершиною множини Р. Одержаний граф позначимо G- і будемо вважати, що він одержаний з графа G внаслідок роздвоювання (розщеплення) вершини V (рис. 45).
Рис.45
Операція з’єднання графів
Операція з’єднання графів (рис. 46), може бути виражена у вигляді добутку (суперпозиції) операції об’єднання графів G і Gi та послідовності операцій введення ребра.
Рис 46.
2.6.3.