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

Пусть G(V, Е) и G’ = (V’, Е’) – два графа. Скажем, что эти два графа изоморфны, если существует пара биективных отображений j: V ®V’, y: Е®Е’ таких, что для любого ребра е = (v₁, v₂)ÎЕ y(е) = (j(v₁), j(v₂)). Иными словами, отображение y переводит ребро, соединяющее две вершины, в ребро, соединяющее образы этих вершин при отображении j.

Изоморфными могут быть на первый взгляд непохожие друг на друга графы.

Изоморфизм этих двух графов задается отображением вершин j: x_i®у_i, i =1,2,3,4; ребро (х_i, х_j) переводится отображением y в ребро (у_i,у_j). Заметим, что данные графы являются полными, то есть вместе с любыми двумя вершинами содержат единственное соединяющее их ребро. Полные графы с n вершинами обозначаются K_n. Ясно, что любые два полных графа с одинаковым количеством вершин изоморфны.

Изоморфизм этих двух графов зададим отображением вершин с помощью подстановки:

(вершина х_i переходит в вершину у_i расположенную под ней; ребро (х_i, х_k) переходит в соответствующее ребро (у_j, у_l), где х_i переходит в у_j, а х_k — в у_l). Как устроен этот изоморфизм ясно: семиугольник с вершинами х₁,…,х₇ переходит в ломаную, составленную из диагоналей семиугольника с вершинами у,…,у; наоборот — диагонали семиугольника слева переходят в стороны семиугольника справа.

неизоморфны, так как у одного из них два цикла длины 4, а у другого – один.