Мал. 2.4. Приклади неорієнтованого (а) і орієнтованого (б) графів
Графи широко застосовуються для уявлення різної інформації про структуру систем і процесів. Прикладами подібних графічних моделей можуть служити: схеми автомобільних доріг, що сполучають окремі населені пункти; схеми телекомунікацій, що використовуються для передачі інформації між окремими вузлами; схеми програм, на яких указуються варіанти галуження обчислювального процесу. Загальною для всіх конкретних подібних моделей є можливість представлення інформації в графічному вигляді у формі відповідного графа. При цьому окремі моделі, як правило, володіють додатковою семантикою і спеціальними позначеннями, характерними для тієї або іншої наочної області.
Важливими поняттями теорії графів є поняття маршруту і шляху, які асоціюються з послідовним переміщенням від вершини до вершини по сполучаючих їх ребрах або дугах. Для неорієнтованого графа маршрут визначається як кінцева або нескінченна впорядкована послідовність ребер S=‹, esl, es2. esk‑ ‑ , таких, що кожні два сусідні ребра мають загальну вершину. Нас цікавитимуть тільки кінцеві маршрути S=‹es1, es2. esk‑ , т. е. такі маршрути, які складаються з кінцевого числа ребер. При цьому ребро esl прийнято вважати початком маршруту S, а ребро esk – кінцем маршруту S. Для орієнтованого графа відповідна послідовність дуг S=‹es1, es2. esk‑ називається орієнтованим маршрутом, якщо дві сусідні дуги мають загальну вершину, яка є кінцем попередньої і початком подальшої дуги.
Прикладами маршрутів для неорієнтованого графа (мал. 2.4, а) є послідовності ребер: S1=‹e1, e2 e5, e8‑ , S2=‹e1, e2, е3, e1‑ , S3=‹e3, e5, e8‑ . Якщо в маршруті не повторюються ні ребра, ні вершини, як у разі S1 і S3, то такий неорієнтований маршрут називається простим ланцюгом.
Прикладами орієнтованих маршрутів для графа (мал. 2.4, би) є такі послідовності дуг: S1=‹e2, e8, e5‑ , S2=‹e3, e7, e6‑ , S3=‹e8, e3, e7, e4, e8‑ . Якщо в орієнтованому маршруті не повторюються ні ребра, ні вершини, як у разі S1 і S2, то такий орієнтований маршрут називається шляхом. Останнє поняття також іноді застосовується для позначення простого ланцюга в неорієнтованих графах і для визначення спеціального класу графів, так званих дерев. В загальному випадку дерева служать для графічного представлення ієрархічних структур або ієрархій, що займають важливе місце в ООАП.
Деревом в теорії графів називається такий граф D=‹V, E‑ , між будь-якими двома вершинами якого існує єдиний простий ланцюг, т. е. неорієнтований маршрут, у якого вершини і ребра не повторюються. Стосовно орієнтованих граф відповідне визначення є складнішим, оскільки грунтується на виділенні деякої спеціальної вершини v0, яка одержала спеціальну назву кореневої вершини або просто – кореня. В цьому випадку орієнтований граф D=‹V, Е‑ називається орієнтованим деревом або скорочено – деревом, якщо між коренем дерева v0 і будь-якою іншою вершиною існує єдиний шлях, що бере почати в v0. Нижче представлено два приклади дерев: неорієнтованого дерева (мал. 2.5, а) і орієнтованого дерева (мал. 2.5, би).
У разі неорієнтованого дерева (мал. 2.5, а) будь-яка з вершин графа може бути вибрана як корінь. Подібний вибір визначається специфічними особливостями вирішуваної задачі. Так, вершина v1 може розглядатися як корінь неорієнтованого дерева, оскільки між v1 і будь-якою іншою вершиною дерева завжди існує єдиний простий ланцюг за визначенням (або, що менш строге, єдиний неорієнтований шлях).
