Page 8 - 4336

Графом (неорієнтованим графом) G називається пара

(2)
(2)
множин (V, E), де E  довільна підмножина множини V (EV );
позначається G=(V, E).

Елементи множини V називаються вершинами графа G, а

елементи множини E  ребрами графа G. Відповідно V

називається множиною вершин, а E  множиною ребер графа G.

Традиційно ребра записуються за допомогою круглих дужок (v,

w).

Нехай задано граф G=(V, E). Якщо (v, w)Е, то кажуть, що

вершини v та w є суміжними, у іншому разі вершини v та w є

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

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

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

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

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

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

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

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

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

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

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

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

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

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

однакові.

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

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

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

8