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

Два графа G₁ = <V₁, E₁> и G₂ = <V₂, E₂> изоморфны ( G₁ ~ G₂) если существует биекция φ: V₁ → V₂ сохраняющие смежность

е₁ = (u,v) E₁ е₂ = (φ (u), φ (v)) E₂

Теорема. Изоморфизм графов есть отношение эквивалентности.

Графы G = <V, E>, G ' = < V ', E ' > изоморфны, если существует такое взаимно однозначное отображение f из V на V ', что для произвольных имеем ( в случае ориентированных графов). Обычно изоморфные графы не различаются между собой.