![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Графи є зручною формою представлення структур обчислювальних систем і процесів, що у них відбуваються.
Визначення. Множина вершин Х, що зв'язані між собою множиною ребер 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, Г> число дуг, що входять у
вершину хі, називається напівступенем заходу р(хі)
" xi (p(xi) ³ |Г-1 (xi)|),
число дуг, що виходять з вершини xi - напівступенем виходу s(xi)
" xi (s(xi) ³|Г (xi)|).
Для неорієнтованого графу рівнобіжні ребра називаються кратними, для орієнтованого графу строго рівнобіжні ребра називаються кратними. Граф без петель і кратних ребер називається простим чи звичайним. Граф без петель, але з кратними ребрами називається мультиграфом, граф, що містить кратні ребра і петлі, називається псевдографом.
Рис. 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. Однорідні графи
Дві вершини xi і xj Î X графу G = <X, V> називають суміжними, якщо вони з'єднані ребром vkÎ V. Для неорієнтованого графу суміжним вершинам відповідає дві пари <xi, xj> і <xj, xi>, для орграфу це пари
<xi, xj>, причому xi - початок дуги, xj - кінець дуги. Вершина xi і ребро (дуга) vk інцидентні, якщо ребро (дуга) входить (виходить) з вершини xi.
Дата публикования: 2014-11-18; Прочитано: 1047 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!