ГЛАВА 2
ИЗОМОРФИЗМ ЧИСЛОВЫХ ГРАФОВ
Числовые графы являются достаточно большим подклассом обычных графов. Они
выделяются, прежде всего, способом представления. В предыдущей главе
рассматривается достаточно обширная литература, в которой исследуются различные
проблемы числовых графов.
Числовым графом называется совокупность непустого множества вершин , непустого
множества образующих и числовой функции смежности , определенной на множестве
всех пар из . Две вершины и , принадлежащие , называются смежными, если .
В данной работе положено начало исследования проблемы изоморфизма на множестве
числовых графов. Известно [29], что для обычных графов задача ИЗОМОРФИЗМ ГРАФОВ
не может быть отнесена ни к классу NP-полных задач, ни к классу полиномиальных
задач. Здесь высказывается гипотеза, что на числовых графах существует
полиномиальный алгоритм распознавания изоморфизма двух графов.
Определение 2.1. Два числовых графа и называются изоморфными, если существует
взаимно однозначное отображение множества на себя такое, что справедливо
соотношение
. (2.1)
2.1 Изоморфизм натуральных арифметических графов
Рассмотрим самые простейшие числовые графы – натуральные арифметические графы с
одной образующей, то есть числовые графы у которых , , а . Для них вопрос об
изоморфизме решает следующая
Теорема 2.1. В классе NA-графов с одной образующей каждому графу с образующей
соответствует множество ему изоморфных, состоящее из
а) трех графов с образующими , , для ;
б) из графов тех же типов, где граф может не существовать при ;
в) из графов первых двух типов, которые могут не существовать для .
Доказательство. При распознавании изоморфных графов используются инварианты
графа, среди которых наиболее важными являются 1) число вершин; 2) число ребер;
3) вектор степеней вершин , выписанный в порядке неубывания . Так как число
вершин у рассматриваемых графов совпадает по условию, а степени вершин у
NA-графов с одной образующей равны 0 или 1, то достаточно проверить совпадение
у всех графов числа ребер.
Рассмотрим матрицу образующих -вершинного полного NA-графа. В ней , а .
. (2.2)
Каждой образующей соответствует диагональ (линия) ортогональная основной
диагонали, все элементы которой равны . Исключение составляют четные , линия
которых пересекается с главной диагональю с нулевыми элементами. Обозначим -
число ребер, соответствующих образующей . Раньше [33] было показано, что .
Образующая называется двойственной к . Для справедливо
. (2.3)
Если решить это уравнение относительно , то получим
. (2.4)
Нетрудно убедиться, что элементы в скобках выражаются один через другой по
формуле
. (2.5)
Таким образом, если NA-граф с одной образующей имеет ребер, то столько же ребер
имеет и NA-граф с образующей . Если еще взять NA-графы с соответствующими
двойственными образующими, то получим еще 2 графа с тем же количеством ребер.
Все четыре графа имеют ребер и изолированных вершин. Очевидно, что все они
изоморфны, что и требовалось доказать.
Пусть . Если , то число ребер графа равно . Такое же число ребер дают и
образующие , и . В результате получим четыре изоморфных графа. Если , то число
ребер графа равно . Такое же число ребер дает и образующая . Но последняя
образующая двойственна сама себе, поэтому добавляется только один изоморфный
граф с образующей , что в сумме дает только три изоморфных графа, а всего
добавляется к исходному графов.
Осталось рассмотреть случай . Если , то граф содержит ребра и ни одной
изолированной вершины. Если уменьшить значение , то число ребер уменьшится.
Если увеличить , то двойственная образующая уменьшится, то есть опять число
ребер уменьшится. Так как самодвойственная образующая, то ей будет
соответствовать единственный граф. Если , то этот случай сводится к и , то есть
получится всего три изоморфных графа. В общем случае к исходному графу
добавляется изоморфных графов. Этим и завершается доказательство теоремы.
На рис. 2.1 приведен пример для NA-графа с и .
Рис. 2.1. Изоморфизмы NA-графа с
Теорема 2.1 дает исчерпывающий ответ об изоморфизме NA?графов с одной
образующей. Однако можно предположить, что NA?граф с одной образующей может
быть изоморфным другому графу с несколькими образующими, если число ребер
одного графа равно сумме ребер другого, а степени вершин обоих графов равны 0
или 1. Некоторые прояснения в этот вопрос вносит следующая
Лемма 2.1. NA-граф с одной образующей не может быть изоморфным NA-графу с
числом образующих больше 2.
Действительно, в этом случае во втором графе найдутся две образующие и ,
которые либо обе меньше , либо обе больше . В первом случае существуют ребра и
, а во втором случае – ребра и . Это означает, что во втором графе либо вершина
1, либо вершина имеют степень, превышающую 1. А это противоречит тому, что
первый граф таких вершин не имеет.
NA-графы с двумя образующими при определенных условиях могут иметь вершины
степень которых не превышает 1. Как следствие леммы 1 можно считать, что для
них , а .
Лемма 2.2. Необходимым и достаточным условиями того, что NA-граф с двумя
образующими имеет степени вершин не больше 1, является
а) ;
б) ;
в) .
(2.6)
Первое условие вытекает из того, что если соответствует только одному ребру, то
это ребро . Тогда максимальное значение соответствует ребру , то есть .
Аналогично, если может представлять только одно ребро, а именно , то
минимальное соответствует ребру , откуда . Максимальный номер для соответствует
ребру , а минимальный номер вершины для соответствует ребру . Чтобы ребра не
были инцидентными, необходимо или , что и требовалось доказать.
Пусть – количество ребер в NA-графе с одной образующе
- Київ+380960830922