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

при синтезе сложных структур (с числом вершин больше 10), возникает проблема синтеза не одинаковых структур. даже одна и та же структура, начерченная разными людьми, не сразу распознаётся (сравните графы рис. 3.1, в и г), хотя эти рисунки содержат одинаковое число узлов и элементов, одинаковый состав элементов, но могут отличаться только связями. Следующее определение [34] позволяет однозначно определять одинаковые структуры.

Два графа Г и G изоморфны, если между множествами V и их вершин существует взаимно однозначное соответствие , сохраняющее отношение смежности вершин, т.е. такое, что для любых и соответствующих им вершин имеет место

, (3.27)

при этом само соответствие называется изоморфизмом графов.

этот формализм означает, что две вершины соединены ребром в одном графе тогда и только тогда, когда в другом графе соответствующие вершины соединены друг с другом.

Пример изоморфных графов приведен на рис.3.1, в и г. При удалении дуги из графа рис.3.1, б получится граф, изоморфный предыдущим. Очевидно, что изоморфные графы должны иметь одинаковое число вершин и ребер. В противном случае они будут различными. Однако наличие равенств не означает изоморфизма двух графов. Например, если в графе рис.3.1, г отсоединить ребро от вершины v₂ и присоединить его к вершине v₃, то изменённый граф с ребром не будет изоморфен исходному, так как исчезнет вершина, к которой в исходном графе подходило только два ребра. в этих двух графах отношение смежности вершин не сохраняется.

Инвариант графа G - это число, связанное с G, которое принимает одно и тоже значение на любом графе, изоморфном G. Число вершин v и число ребер q являются инвариантами графа. В связи с вышеизложенным, для вершин v_i введём дополнительную характеристику.

Степенью вершины v_i графа Γ=(V,Â) называется число ребер инцидентных этой вершине. В изоморфных графах G и G степени соответствующих вершин должны быть равными . В предыдущем примере степени всех вершин изменённого графа G такие: 4,3,3,3,3. Степени вершин исходного графа Г – 4,4,3,3,2 существенно отличаются от степеней вершин графа G, но сумма degv_i в обоих графах одинакова и равна 2q, потому что число рёбер у них одинаково, а каждое из них инцидентно двум вершинам. Это свойство графов было установлено Эйлером и является, по-видимому, первым утверждением теории графов:

. (3.28)

В произвольном графе, содержащем v вершин и q рёбер - (v, q)-графе для любой вершины v_i справедливо неравенство

. (3.29)

Граф, у которого имеются вершины со степенью, состоит из нескольких компонент не связанных между собой рёбрами, причём эти компоненты называют подграфами, вершины с указанной степенью называют изолированными, а сам граф – несвязным. Вершины с называют концевой или висячей. Граф со всеми вершинами одинаковой степени называют однородным. набор степеней вершин подобно числу вершин и числу рёбер является инвариантом графа.

В теории чисел разбиение целого неотрицательного числа Q определяют как набор целых положительных чисел, сумма которых равна Q. Разбиение Q графа – это представление числа 2q в виде (3.28). Разбиение числа Q на v частей называют графическим, если существует граф со степенями . Упорядочим степени вершин неразделимого⁶ графа в порядке невозрастания. Тогда каждое разбиение

, (3.30)

выделяет класс изоморфных связных графов [33].

Нижеследующий алгоритм построения всех возможных разбиений Q_i был разработан Д.А. Скойбедо совместно с автором и опубликован в приложении П-2 учебника [1]. У первого разбиения Q₁ первое число p₁ выбирается наибольшим, позволяющим выполнить неравенства из (3.30), но не превышающим v-1, т.е.

, (3.31)

а все остальные числа p_i выбираются из следующего соотношения:

Разбиение Q₂ образуется из Q₁ путём уменьшения числа p₁ на единицу и добавления её к p₂ , если ; или к p₃, если и так далее. Остальные разбиения Q_i получаются аналогично постепенным уменьшением чисел p₁, p₂, p₃,… на единицу. Признаком формирования всех разбиений служит невозможность дальнейшего вычитания единицы из любого p_i и добавления её к числу p_j c номером без нарушения условий (3.32). Последнее разбиение часто имеет равными все числа p_i.

пример1. образуем все Q_i для графов Г(6,8). Сначала находим p₁=v-1=6-1= =5. Затем определяем

Оставшиеся степени равны p_i=2. Таким образом, в качестве первого разбиения имеем Q₁=(5, 3, 2, 2, 2, 2). Следующее разбиение построим, уменьшив p₁, т.е. Q₂=(4, 4, 2, 2, 2, 2). Уменьшая на единицу последовательно p₂ и p₁ и добавляя её соответственно к p₃ и p₄ , получим Q₃=(4, 3, 3, 2, 2, 2) и Q₄ =(3, 3, 3, 2, 2, 2).

Рассмотренный алгоритм построения всех разбиений можно иначе представить как нахождение всех решений системы:

Ниже приводится одна из возможных процедур решения этой системы:

Если i₁ не существует, т.е. то решения системы (3.33) исчерпаны, в противном случае – перейти на метку L.

Проблема изоморфизма графов в определённой степени усугубляется произвольным обозначением его вершин. Так как разбиение Q включает в себя инварианты, определяемые числом вершин и ребер, то произведём упорядочение обозначений вершин согласно его разбиению. Изоморфные графы G и G' имеют такие матрицы смежности D и D', что одна из них, например D', может быть получена из другой матрицы D путем одинаковой перестановки строк и столбцов с помощью подстановки h, принадлежащей симметрической группе матриц-подстановок H_v, т. е.

. (3.34) (1)

На графе группе H_v эквивалентна транзитивная группа L_v, действующая на множестве V. При большой размерности матрицы D число перестановок строк и столбцов становится столь значительным (v!), что прямой перебор, согласно формуле (3.34-1) оказывается неприемлемым. Это так называемое NP-полное решение. Поэтому для уменьшения числа сравнений матриц D и применим вектор степеней вершин, получающийся в результате разбиения числа 2q согласно (3.30). При графе, заданном матрицей D, числа p_i находят, суммируя элементы строки или столбца i матрицы D.

На множестве V введем отношение эквивалентности:

,

разбивающее V на множество орбит O = {O_k}, k = группы L_v. Все элементы v_iV орбиты O_k характеризуются одной и той же степенью вершин p_i графа. Присвоим индексу степени p_i индекс орбиты k, если v_iO_k, т. е.

и назовем длиной l_k орбиты O_k число ее элементов. Чтобы указанное разбиение использовать для уменьшения числа изоморфных графов, упорядочим строки и столбцы матрицы согласно разбиению Q [3]

(3.35)

Теперь каждая подстановка h_kH_v переставляет элементы, соответствующие только одной орбите O_k, оставляя неподвижными оставшиеся элементы V \ O_k. Поэтому число различных перенумераций вершин графа на новом множестве L_v' равно уже не v!, а .

Пример2. Определим изменение числа изоморфных графов после упорядочивания номеров его вершин в соответствии с разбиением Q. У графа Г(7,9) (рис. 3.4,ж) первоначальная нумерация вершин принята как обычно, по часовой стрелке (цифры без скобок). Так как порядок нумерации вершин не связан с параметрами конкретного графа, то число всех изоморфных графов равно 7!=5040. Для такого простого графа это число весьма не малое.

введём правило нумерации вершин согласно его разбиению: первый номер присваивается вершине с максимальной степенью, последний номер – вершине с минимальной степенью. Вершины, имеющие одинаковые степени, принадлежат одной орбите, т.е. с этой точки зрения эквивалентны, и их нумерация внутри одной орбиты произвольна. число изоморфных графов для рассматриваемого примера будет всего , что в 104 раза меньше произвольной нумерации вершин, причём матрицы D и имеют вид

.

Над столбцами матриц D и D_Q указаны соответственно номера вершин и степени вершин согласно Q.

Дальнейшего уменьшения числа изоморфных графов можно добиться укорочением длины l_k за счет введения нового отношения эквивалентности на вершинах графа. это отношение, сохранив предыдущее, должно разбить элементы орбиты O_k на множество подклассов O_k = {z_kr}, r = . С увеличением числа s_k уменьшается длина подкласса z_kr, а число возможных перенумераций вершин графа станет меньшим . Для этого в [2] предложено в матрице D_Q заменить d_ij=1 на элемент d_ij=t_ij, где число t_ij 0 отражает дополнительно какую-либо одну или несколько характеристик вершин j и ребра (i,j). Пусть, например, сначала такой характеристикой является только степень вершины j, т.е. t_ij=p_j=degv_j. тогда можно сформировать матрицу с новыми элементами

(3.36)

которую не трудно образовать из матрицы D_Q :

(3.37)

Здесь элементы диагональной матрицы составлены в соответствии с разбиением Q. Используем симметрию матрицы для введения эквивалентности. Из ненулевых элементов каждой i-ой строки матрицы образуем вектор , элементы которого упорядочены по невозрастанию . считаем вершины v_i,v_jO_k эквивалентными, если равны соответствующие им векторы:

v_i ~ v_j <=>(t_ik)=(t_jk): t_i1 = t_j1, t_i2 = t_j2,…,.

Множество вершин v_iO_k , соответствующих попарно эквивалентным векторам, образует класс эквивалентности Z_kr, а каждая орбита содержит некоторое число этих классов r = . В случае, если все вершины орбиты различны, то на ней перенумерация вершин невозможна, а следовательно не образуются изоморфные графы. если все вершины орбиты эквивалентны, то с помощью перенумераций только этих вершин образуется l_kr! изоморфных графов. Упорядочим номера вершин v_iO_k на основании лексикографического⁷ порядка векторов t_km и t_kl , вершины которых принадлежат разным классам. Если выполняется неравенство

, (3.38)

то присвоим v_mZ_kr и соответствующим векторам t_m номера m<l. Из упорядоченных векторов t_i образуем смежностно-степенную таблицу T (ССТ), не содержащую нулевые элементы, а также отражающей степени вершин, с которыми смежна вершина i, а не их номера, как в матрице .

В таблице (3.39) слева от черты выписаны степени вершин, в соответствии с разбиением Q; t_ij – степень t вершины смежной с вершиной , расположенной в её строке на месте ; строки разбиты в соответствии с множеством орбит O = {O_k} и упорядочены

. (3.40)

Затем lk строк, соответствующих длине O_k, заново разбиты согласно множеству классов эквивалентности {Z_kr} и лексикографически упорядочены

r, r+1I; t_kr > t_k(r+1) => vrZ_kr, vr+1Z_k(r+1), (3.41)

Отсюда следует:

Утверждение. различным смежностно-степенным таблицам (ССТ) T соответствуют неизоморфные графы.

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

Пример 3. Рассмотрим все связные графы Г(7,9) (рис. 3.6) соответствующие одному разбиению Q =(4,3,3,2,2,2,2). Графы б), в), з), л) – являются разделимыми в вершине сочленения, а граф д) – содержит мост. У всех графов три орбиты: O₁={p₁|4}, O₂={p₂|3,3}, O₃={p₃| 2,2,2,2}, у которых длина соответственно равна: l₁=1, l₂=2, l₃=4.

Теперь для каждого графа рис. 3.5 построим таблицы (3.37) в соответствии с условиями (3.38) и (3.39). В результате получим таблицы (3.40), среди которых имеются одинаковые (), но они отражают различные графы соответственно: в) и г); д) и е); и) и к).

Если необходимо построить все графы, то помимо степени вершин можно ввести ещё один их параметр, например их смежность. Этот вариант построения таблиц T будет рассмотрен в конце данного параграфа, так как он рассчитан на применение ЭВМ.