Основні визначення

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

Визначення. Множина вершин Х, що зв'язані між собою множиною ребер V, називається графом і позначається G = <X,V>.

Приклад. Граф (рис. 14.1) G = <{x1, x2, x3, x4}, {v1, v2, v3, v4, v5}>

Рис. 14.1. Граф як пара множин

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

Визначення. Граф G – це двійка вигляду G = < X, Г >, де Х – множина вершин графу, Г – відповідність, що відбиває множину вершин Х саме в себе.

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

Приклад. Граф (рис. 14.2) тільки з нестрого рівнобіжними дугами (ліворуч) представляється другим визначенням G=<{x1, x2}, {(x1, x2), (x2, x1)}>, але графи з рівнобіжними дугами і ребрами – ні (праворуч).

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

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

Рис. 14.2. Графи з не строго рівнобіжними дугами
і рівнобіжними ребрами

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

Рис. 14.3. Строго рівнобіжні і не строго рівнобіжні дуги,
ребро, отримане з нестрого рівнобіжних дуг, і петля

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

Рис. 14.4. Неорієнтований граф, орграф і змішаний граф

Для неорієнтованого графу число ребер, що зв'язані з вершиною х_і, називається ступенем вершини G(х_і), причому петля враховується двічі.

Для орієнтованого графу G=<X, Г> число дуг, що входять у
вершину х_і, називається напівступенем заходу р(х_і)

" x_i (p(x_i) ³ |Г^-1 (x_i)|),

число дуг, що виходять з вершини x_i - напівступенем виходу s(x_i)

" x_i (s(x_i) ³|Г (x_i)|).

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

Рис. 14.5. Мультиграф і псевдограф

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

Рис. 14.6. Повний граф

Якщо вершини Х простого графу допускають таку розбивку на дві непересічних підмножини Х1 і Х2 (Х1 Ç Х2 = Æ і Х1 È Х2 =Х), що не мають ребер, які з'єднують вершини тої самої підмножини, то він називається двочастковим чи біграфом.

Приклад. Біограф (рис. 14.7), у якому X = {x1, x2, x3, x4, x5, x6}, X1 = {x1, x2, x3}, X2 = {x4, x5, x6}

Рис. 14.7. Двочастковий граф (біграф)

Граф, ступені вершин якого однакові і рівні “r”, називається однорідним, чи регулярним r-го ступеня.

Рис. 14.8. Однорідні графи

Дві вершини x_i і x_j Î X графу G = <X, V> називають суміжними, якщо вони з'єднані ребром v_kÎ V. Для неорієнтованого графу суміжним вершинам відповідає дві пари <x_i, x_j> і <x_j, x_i>, для орграфу це пари
<x_i, x_j>, причому x_i - початок дуги, x_j - кінець дуги. Вершина x_i і ребро (дуга) v_k інцидентні, якщо ребро (дуга) входить (виходить) з вершини x_i.