Page 14 - 4386

мають n і m вершин відповідно, він позначається K . Кількість
n,m
ребер повного двочасткового графа K складає n·m. Наприклад,
n,m
повний двочастковий граф K називається зірковим графом або
1,n
зіркою та має відповідно n ребер (рис. 1.6 б).

а б

Рисунок 1.6 – Приклади повного двочасткового (а)

та зіркового (б) графів

Кажуть, що граф “укладається на площині”, якщо він

ізоморфний (однаковий за формою) графу, вершини якого є

точками площини, а ребра – неперервними лініями площини без

самоперетинів, що з'єднують відповідні вершини, причому жодні

два ребра не мають спільних точок, крім вершини, інцидентної їм

обом.
Планарним називається граф, який можна укласти на

площині, плоским – граф, який уже укладено на площині
(рис. 1.7). Таким чином планарним називається граф, ізоморфний

деякому плоскому графу.

а б

Рисунок. 1.7 – Планарний (а) та відповідний йому плоский

граф (б). Пунктиром показано перенесені вершини та ребра

13