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

Определение 9.4. Говорят, что два графа G1 (V,Е) и G2 (V,Е) - изоморфны (обозначается G 1 ~ G 2), если существует биекция Н: V ₁Þ V ₂, сохраняющая смежность e ₁=(u, v)Î E ₁. Из этого и наличия биекции следует, что е ₂(h (u), h (v))Î E ₂. Изоморфизм графов есть отношение эквивалентности. Действительно, изоморфизм обладает всеми необходимыми свойствами:

1) рефлексивность G 1 ~ G 2, где требуемая биекция есть тождественная функция,

2) симметричность если G 1 ~ G 2 с биекцией h, то G 2 ~ G 1с биекцией h ^-1,

3) транзитивность если G 1 ~ G 2с биекцией h и G 2 ~ G 3с биекцией g, то G 1 ~ G 3 с

биекцией hg.

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

Пример:

Три внешне различные диаграммы являются диаграммами одного и того же графа:

Определение 9.5. Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, р (G) и q (G) — инварианты графа G. Неизвестно никакого набора инвариантов, определяющих граф с точностью до изоморфизма

Пример:

Количество вершин, ребер и количество смежных вершин для каждой вершины не определяют граф. Ниже представлены диаграммы графов, у которых указанные инварианты совпадают, но графы при этом не изоморфны