Page 9 - 6769

Вершини графа підпорядковані елементам певної множини
Х = {x1, x2, ∙∙∙ , xn}.
На рис. 3.1 вершини графа позначено літерами A, B, C, D.
Кількість вершин графа дорівнює кількості елементів множини X, у
нашому випадку - 4. Кількість вершин в графі позначимо q.
Ребро (дуга) графа — відрізок неперервної лінії, що в
загальному випадку з’єднує будь-які дві вершини. Кількість ребер в
графі позначимо p.
Графи поділяють на орієнтовані (спрямовані) та неорієнтовані.
Напрям орієнованого ребра вказують стрілкою. Ребра позначають
літерами або цифрами (на рис. 3.2 – 1, 2, 3, …,). Ребро,. яке виходить та
входить в одну й ту саму вершину, називають петлею. Надалі
вважатимемо, що ребер у вигляді петлі не існує. Множину ребер
позначимо символом U.
Орієнтований граф – граф у якого всі ребра орієнтовані.
Формально граф визначається як сукупність множин вершин Х
і ребер U у вигляді G = (X, U). Відтепер ми будемо розглядати тільки
орієнтовані графи.
На рис. 3.2 зображено звичайний (а) та орієнтований (б) граф.

Рисунок 3.2 – Приклад звичайного та орієнтованого графів

Із частини графа G = (X, U) можна утворити підграфи. На рис.
3.3, а, б, в, г зображено деякі підграфи графа, показаного на рис. 3.2.
Підграфи можуть мати не всі вершини та ребра графа.

9