Page 20 - 4386

На рис. 1.12 (а, б, в) зображені підграфи графа, зображеного

на рис. 1.12 г. Причому, підграф (рис. 1.12 б) є його суграфом.

а б в г

Рисунок 1.12 – Приклади графу та його підграфів

1.7 Ізоморфізм графів

Буквальний переклад слова “ізоморфізм” означає

“однаковість форми”. Форма графа – це його структура. Таким

чином, ізоморфізм графів означає однаковість їх структури.

Два графи G =(V , E ) і G =(V , E ) називаються
2
2
1
1
2
1
ізоморфними (це позначається G ≅G ), якщо між множинами їх
2
1
вершин існує взаємно однозначне відображення ϕ: V →V , яке
2
1
зберігає суміжність, тобто для довільних вершин v та w ребро
(v, w)∈E тоді і тільки тоді, коли ребро (ϕ(v), ϕ(w))∈E (рис. 1.13).
1
2
При цьому ϕ називається ізоморфним відображенням або
ізоморфізмом графа G на граф G . Іншими словами, графи G та
1
1
2
G ізоморфні, якщо їхні вершини можна занумерувати таким
2
чином, що ребро e тоді і тільки тоді з'єднує вершини v та w у
i
графі G , коли ребро e ´ з'єднує вершини v´ та w´ у графі G .
i
2
1
Таким чином, ізоморфні графи відрізняються фактично
лише ідентифікаторами (іменами) своїх вершин. З точки зору

теорії графів, ця відмінність не є суттєвою, тому звичайно

ізоморфні графи ототожнюють і, зображаючи графи у вигляді

діаграм, або зовсім не ідентифікують їхні вершини, або

нумерують вершини натуральними числами.

19