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

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

Визначення. Множина вершин Х, що зв'язані між собою множиною ребер 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)|).

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