Список літератури Основна

1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.148-157.

2. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.174-182.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. – М.: Лаборатория Базовых Знаний, 2001. - С.39-49, 53-66.

Додаткова

4. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.47-55.

5. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.13-20.

6. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. - С.25-29.

Для практичних занять

7. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.23-24.

8. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.249-281.

Розділ III. Графи

Лекція 14. Визначення і представлення графів

Вступ

Лекція має за мету навести базові визначення і поняття теорії графів. Розглянути висловлення, визначення та компоненти графів, неорієнтовані та орієнтовані графи, спеціальні види графів, способи завдання неорієнтованих та орієнтованих графів. Звернено увагу до визначення ізоморфних графів.

У лекції присутні два підрозділи:

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

2. Способи представлення графів

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

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

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