2014-02-02
4186
Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) называются изоморфными, если существует биекция j: V 1® V 2, которая сохраняет отношение смежности между вершинами графа:
" u, v Î V 1 ({ u, v }Î E 1Û{j(u),j(v)}Î E 2).
В следующем примере биекция 
является изоморфизмом графов.
Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) могут быть неизоморфными, если:
1) 
;
2) 
;
3) для каждого 
графы имеют различные числа вершин степени 
.
Графы могут быть неизоморфными, даже если все перечисленные три условия выполнены:
