Page 13 - 4386

з'єднана більш ніж одним ребром або більше ніж двома дугами

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

а б в г

Рисунок 1.4 – Види графів: а – орієнтований; б – неорієнтований

граф; в – змішаний граф; г – порожній граф

Якщо декілька ребер є інцидентні одній і тій самій парі

вершин, то такі ребра називаються кратними (зустрічаються в

мультиграфах).

Граф без петель і кратних ребер називається повним, якщо

кожна пара його вершин з'єднана ребром. Повний граф з n

вершинами позначається K . Якщо граф G=(V, E) є повним, то за
n
(2)
означенням E=V . На рис. 1.5 зображено повні графи К , К , К ,
4
3
2
К і К відповідно.
6
5

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

Окремий клас графів утворюють двочасткові графи. Граф

G=(V, E) називається двочастковим, якщо множину його вершин

V можна так розбити на дві підмножини V і V (частки), що
2
1
кожне ребро графа з’єднує вершини з різних часток, тобто

(2)
E⊆V \(V 1 (2) ∪V 2 (2) ). Двочастковий граф називається повним
двочастковим, якщо будь-які дві вершини з різних часток

суміжні (рис. 1.6 а). Якщо частки повного двочасткового графа

12