Page 12 - 4386

несуміжними. Якщо е=(v, w) − ребро графа, то вершини v та w

називаються кінцями ребра е. У цьому випадку кажуть також, що

ребро е з’єднує вершини v та w. Вершина v і ребро е називаються

інцидентними, якщо v є кінцем е.

Два ребра називаються суміжними, якщо вони мають

спільну вершину (інцидентні до загальної вершини).

Ребро, початок і кінець якого знаходиться в одній і тій самій

вершині графа, називається петлею.

Вершини, не зв’язані з іншими, називаються ізольованими.

Необхідно відзначити, що при зображенні графа, не всі

деталі рисунку мають значення. Так, наприклад, несуттєвою є

довжина і кривизна ребер, взаємне розташування вершин на

площині. Принциповим є тільки відношення інцидентності.

Моделі, зображені рис. 1.3 (а, б, в), з погляду теорії графів

однакові.

У деяких задачах інцидентні ребру вершини нерівноправні,

а розглядаються в певному порядку. Тоді кожному ребру можна

приписати напрямок від першої інцидентної вершини до другої.

Напрямлені ребра називають орієнтованими ребрами або

дугами, перша по черзі вершина називається початком дуги, а

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

орієнтованим графом або орграфом (рис. 1.4 а), а граф, що не

містить напрямлених ребер – неорієнтованим або н-графом (рис.

1.4 б). Граф, у якому присутні і ребра і дуги називається

змішаним графом (рис. 1.4 в). Множина ребер графа може бути

порожньою (рис. 1.4 г). Такий граф називається порожнім або

нуль-графом. Тривіальним називається граф з однією вершиною і

без ребер. Мультиграф – це граф, в якому існує пара вершин, що

11