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

Той самий граф геометрично можна зобразити різноманітними способами. Так, на рис.2.8 наведені три зображення того самого графа. Такі графи називаються ізоморфними.

Рис. 2.7. Граф у формі дерева
Довільна підстановка j на множині вершин графа G, що зберігає відношення суміжності, тобто така, що уяви j(u) і j(v) вершин u і v суміжні тоді і тільки тоді, коли суміжні самі вершини u і v , називається автоморфізмом графа G. Іншими словами, автоморфізм графа - це ізоморфізм графа на себе.

 

1

1 2

2

1 4 3 4

4 3

 
 


Рис.2.8. Приклад ізоморфних графів 2 3

 

Довільний граф G має щонайменше один автоморфізм - тотожне перетворення е: VG ® VG, при якому e(v) = v для будь-якої вершини v. Очевидно, що якщо j - автоморфізм графа G, то й обернена підстановка j-1 також є автоморфізмом. Якщо підстановки j і f обидві є автоморфізми, то і їхній добуток jf - автоморфізм.