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

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

Изоморфизмом называют взаимно однозначное соответствие между множествами вершин двух графов и , сохраняющее отношение смежности, а сами графы называются изоморфными. Автоморфизмом называется изоморфное отображение графа на себя. Примеры изоморфных графов показаны на рис. 3. Для установления изоморфности достаточно составить списки вершин всех графов, указав для каждой из них все ее соседние вершины. В данном случае все эквивалентные вершины пронумерованы одинаково, что упрощает решение задачи. Задача усложняется, если эквивалентные вершины имеют разные номера. В этом случае процедуру работы со списками придется повторять неоднократно, каждый раз меняя нумерацию вершин одного из графов, пока не будет обнаружен изоморфизм, т. е. получены идентичные списки вершин. В худшем случае потребуется проверить вариантов нумерации вершин. Доказать неизоморфизм графов можно, только выполнив все проверки. Существенно сократить их количество можно, если использовать инварианты.

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

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

Оценку сверху для числа попарно неизоморфных графов дает следующая теорема.

Теорема 2. .

Доказательство. Очевидно, что число вершин в каждом из рассматриваемых графов не превосходит .Занумеруем их числами 1, 2, …, . Каждое ребро определяется двумя вершинами (концами), не обязательно различными, так что для каждого ребра имеется не более возможностей выбора концов, а для ребер – не более, чем . Следовательно, . Используя неравенство , получаем Теорема доказана.