3.1.2. Изоморфизм, гомеоморфизм
Определение. Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G1, равно число ребер, соединяющих соответствующие вершины в G2.
Из определения следует, что изоморфные графы можно одинаково изображать графически и отличаться они будут только метками вершин.
Изоморфизм графов есть отношение эквивалентности.
Пример 70.
На рисунке 21 изображены три изоморфных графа. На рисунке 22 изображены два неизоморфных графа.
Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.
Пример 71.
С точностью до изоморфизма существует ровно четыре простых графа с тремя вершинами и одиннадцать с четырьмя вершинами. Постройте эти графы.
Решение.
1. Построим четыре простых графа с тремя вершинами с точностью до изоморфизма (рис. 23):
2. Построим одиннадцать простых графов с четырьмя вершинами с точностью до изоморфизма (рис. 24):
Определение. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.
Определение. Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.
Определение. Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.