Page 11 - 4386

̅ A⊕B

Рисунок 1.2 – Діаграми Вена

1.3 Основні поняття теорії графів. Типи графів

Граф задається множиною точок або вершин v , v , ..., v і
1
2
n
множиною ліній або ребер e , e , ... , e , що з'єднують між собою
1
2
m
всі або частини точок (рис. 1.3).

а б в

Рисунок 1.3 – Приклади графів

Нехай V − деяка непорожня скінченна множина, а V (2) −

множина всіх двохелементних підмножин (невпорядкованих пар

різних елементів) множини V.

Графом (неорієнтованим графом) 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 є

10