Означення графів, різновиди графів

Означення неорієнтованого графа

Нехай V - деяка непуста множина. Позначимо V⁽²⁾ - множину всіх неупорядкованих різних двоелементних підмножин множини V, a MV⁽²⁾ - мультимножину множини V⁽²⁾, тобто в MV⁽²⁾ можуть входити однакові пари елементів із V, причому цих пар може бути скільки завгодно.

Неорієнтованим мультиграфом G називається пара (V, Е), де E cξ MV^{K_n. На рис. 35 зображені графи IC₄ і K₅.}

Рис. 34

Регулярні графи

Більш загальними, ніж повні є регулярні графи. Граф називається регулярним, або однорідним, якщо його вершини мають один і той же степінь. Якщо степінь кожної вершини дорівнює к, то граф називається регулярним графом степеня к. Отже, повний граф п-го порядку є регулярним графом степеня п - 1. Регулярні графи степеня 3 (рис. 36) називають також кубічними, або тривалентними графами.

Рис.36

Повністю незв’язані графи

Граф, множина ребер якого пуста, називається повністю незв’язаним або пустим. Незв’язаний граф з п вершинами позначається N_n. Кожний пустий граф є регулярним графом степеня 0.

Платонов! графи

Платановими графами називаються графи, утворені вершинами і ребрами п’яти правильних многогранників - платонових тіл: тетраедра, куба, октаедра, додекаедра та ікосаедра. Графи, зображені на рис. 37, відповідають тетраедру, кубу і октаедру.

Рис.37

Двочастинні графи

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

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

Повний двочастинний граф (рис. 38) Ki_n називається зірковим графом.

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

Повний двочастинний граф K₅

Рис.38

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

Граф G = (V, Е) називається орієнтованим графом (орграфом) якщо E ⊂ V², тобто вершини всіх його ребер упорядковані. Якщо (u, v) ∈ Е, то вершину u називають початковою вершиною, a v - кінцевою вершиною ребра. Орграфи зображуються так як і графи, з тією лише різницею, що їх ребра позначаються стрілками, які ведуть з початкової вершини в кінцеву.

Граф G = (V, Е) називається орієнтованим мультиграфом, якщо E cξ MV² і кожне його ребро упорядковане, тобто вказано, яка вершина перша, а яка друга. Отже, в орграфах ребра (u, v) і (v, н) різні

Ізоморфізм графів. Підграфи

Нехай G = (V, Е), H = (V_b Ei) - графи і взаємооднозначна відповідність (тобтоВідображення h

називається ізоморфізмом графів G і Н, якщо для будь-яких вершин u і v графа G їх образи h(u) і h(v) суміжні в графі H тоді і лише тоді, коли u і V суміжні в графі G. Якщо таке відображення h існує, то графи G і H називаються ізоморфними. Відношення ізоморфізму графів є відношенням еквівалентності. Ізоморфні графи як правило не розрізняються.

190

2.6.2.