Определение. Два графа G₁ и G₂ называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G₁, равно число ребер, соединяющих соответствующие вершины в G₂.

Из определения следует, что изоморфные графы можно одинаково изображать графически и отличаться они будут только метками вершин.

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

Пример 70.

На рис. 3.3 изображены три изоморфных графа. На рис. 3.4 изображены два неизоморфных графа.

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

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

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример 71.

С точностью до изоморфизма существует ровно четыре простых графа с тремя вершинами и одиннадцать с четырьмя вершинами. Постройте эти графы.

Решение.

1) Построим четыре простых графа с тремя вершинами с точностью до изоморфизма (рис. 3.5):

Рис. 3.5. Простые графы с тремя вершинами с точностью до изоморфизма

2) Построим одиннадцать простых графов с четырьмя вершинами с точностью до изоморфизма (рис. 3.6):

Рис. 3.6. Простые графы с четырьмя вершинами

Определение. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг  (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение. Орграф D₁ называется подразбиением орграфа D₂, если орграф D₁ можно получить из D₂ путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Определение. Орграфы  D₁,  D₂ называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.