Page 75 - 4496

а) б)
Рисунок 3.9 – Графи з хроматичним числом 3

Розглянуті питання пов'язані з відомою проблемою
чотирьох фарб. Для того щоб її сформулювати, нам
знадобляться ще кілька визначень.
Граф називається плоским, якщо він намальований на
площині, причому будь-які 2 ребра можуть перетинатися
тільки у вершині.
Графи називаються ізоморфними, якщо існує така
нумерація вершин у цих графах, що вони мають ту саму
матрицю суміжності (фактично ізоморфні графи – це однакові
графи, які відрізняються тільки іншим зображенням).
Граф називається планарним, якщо він ізоморфний
плоскому графу. Таким чином, планарний граф можна
зобразити на площині як плоский. На рис. 3.10 зображені 2
ізоморфних (однакових) графа, причому перший з них
планарний, а другий є плоским.

Рисунок 3.10 – Ізоморфні графи

72