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

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

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

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

3) транзитивность если G1 ~ G2с биекцией h и G2 ~ G3с биекцией g, то G1 ~ G3 с

биекцией hg.

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

Пример:

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

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

Пример:

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