Изоморфизм графов.

Один и тот же граф геометрически можно изобразить различными способами. Так на рис. 2.7 приведены три изображения одного и того же графа. Такие графы называются изоморфными.

 

1

1 2

2

1 4 3 4

4 3

2 3

Рис.2.7 - Пример изоморфных графов

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