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

Определение 4.1. Два графа G = (V, U) и G’ = (V’, U’) называются изоморфными (обозначается G ≅ G’ ), если между их множествами вершин существует взаимно однозначное соответствие (биективное отображение), сохраняющее инцидентность ребер, т.е. если φ: V⟶V’ – биективное отображение между множествами вершин, то

ребро { v_i, v_j} ∊ U тогда и только тогда, когда ребро {φ( v_i), φ(v_j)} ∊ U’ (для орграфов ( v_i, v_j) ∊ U ⇔ (φ(v_i), φ(v_j)) ∊ U’ ).

Можно дать и другое, эквивалентное предыдущему, определение изоморфизма графов:

Определение 4.2. Два графа G = (V, U) и G’ = (V’, U’) называются изоморфными (обозначается G ≅ G’ ), если между их множествами вершин и множествами ребер (дуг) существуют взаимно однозначные соответствия (биективные отображения) φ: V⟶ V’ и ψ: U⟶ U’ такие, что ( v_i, v_j) ∊ U ⇔ ψ (v_i, v_j) =(φ(v_i), φ(v_j)) ∊ U’.

Изоморфизм объектов в математике играет очень важную роль и в дальнейшем нам придется довольно часто встречаться с изоморфными объектами (структурами) как в дискретной математике, так и в других разделах математики. Интерес к изоморфным объектам вызван тем, что с математической точки зрения они отождествляются (не различаются), ибо имеют абсолютно одинаковые свойства, хотя по виду эти объекты могут различаться очень существенно. Из определения изоморфизма графов сразу следует, что изоморфные графы – это по сути один и тот же граф, но с различным обозначением (или нумерацией) вершин. Отсюда следуют:

Теорема 4.1. Два графа изоморфны между собой тогда и только тогда, когда матрицу смежности одного из них можно получить из матрицы смежности другого с помощью одновременной перестановки строк и столбцов этой матрицы (т.е. одновременно с перестановкой i–той и j–той строк матрицы осуществляется и перестановка i–того и j–того столбцов матрицы).

Теорема 4.2. Два графа изоморфны между собой тогда и только тогда, когда матрицу инцидентности одного из них можно получить из матрицы инцидентности другого с помощью перестановок строк и столбцов этой матрицы.

Пример 4.1. Выяснить, изоморфны ли графы G и G’, где

х₁ х₆ у₁ у₇ у₆

G: х₇ х₅ G’: у₃ у₅

х₂ х₃ х₄ у₂ у₄,

Решение. Заметим, прежде всего, что количества вершин первого и второго графов совпадают, а потому взаимно однозначное соответствие (биективное отображение) между множествами вершин установить можно. Но необходимо такое соответствие, которое сохраняло бы инцидентность. Учтем, что вершины разной степени соответствовать друг другу не могут, ибо инцидентны разным количествам ребер (т.е. такое соответствие не сохраняло бы инцидентность). Поэтому подсчитаем степени вершин графов. Имеем:

в графе G в графе G’

deg(t) = 2:x₁, x₂, x₄, x₇y₂, y₄, y₅, y₆

deg(t) = 3:x₅ y₁

deg(t) = 4: x₆ y₃

deg(t) = 5: x₃ y₇

Поскольку вершин степеней 3,4,5 в графах по одной, то они и должны быть сопоставлены друг другу соответственно. Оформим искомое биективное отображение в виде подстановки

.

Убеждаемся в том, что уже установленное соответствие вершин сохраняет инцидентность (например, ребра { x₃,x₅ }, { x₃,x₆ }{ x₅,x₆ } в графе G существуют и им отвечают в графе G’ соответственно ребра { y₇,y₁ }, { y₇,y₃ }, { y₁,y₃ }). Соответствие оставшихся вершин перебором требует большого количества проверок инцидентности. Можно, в нашем случае, заметить, что в графе G вершина x₃ степени 5 не соединена ребром с вершиной x₁ степени2. Тогда и в графе G’ вершина y₇ не должна соединяться ребром с вершиной степени 2. Таковой вершиной в графе G’ является вершина y₄. Поставим в соответствие вершине x₁ вершину y₄ и проверим наличие соответствующих ребер. Продолжим дальнейший анализ и окончательно получим

Таким образом, биективное отображение между множествами вершин исходных графов, сохраняющее инцидентность, установлено и потому эти графы изоморфные друг другу.

Как видим, установление изоморфизма двух графов – процедура довольно громоздкая. Иногда о неизоморфности графов можно судить по косвенным характеристикам графов.

Пример 4.2. Проверить изоморфизм графов G и G’, где

v₁ v₂ v₁ v₂

G: G’:

v₃ v₄ v₃ v₄

v₅v₆ v₅v₆

Количества вершин исходных графов (шесть) и ребер (восемь) одинаково. Поэтому биективные отображения между множествами вершин и ребер соответственно установить можно. Дальнейший перебор вариантов соответствия вершин для поиска соответствия, сохраняющего инцидентность соответствующих ребер, громоздок. Однако можно сразу заметить, что в графе G имеются два цикла длины 3 (v₁,v₃,v₅ и v₂,v₄,v₆), а граф G’ циклов длины 3 вообще не имеет. Ранее мы отмечали, что изоморфные графы имеют абсолютно одинаковые свойства. Поэтому мы можем сразу судить о том, что исходные графы изоморфными не являются.

Замечание 4.1. Установление изоморфизма орграфов происходит аналогично описанному выше с той лишь разницей, что при установлении биективного отображения между множествами вершин необходимо учитывать не просто степени вершин, а их полустепени захода и исхода.

Дата добавления: 2014-12-16