On a new complete invariant for acyclic graphs.pdf В задаче проверки изоморфизма графов (задача ИГ) даны два обыкновенных графас одинаковым числом вершин и ребер. Необходимо ответить на вопрос, существуетли такое биективное отображение (изоморфизм) множества вершин одного графа намножество вершин второго, которое сохраняло бы смежность соответствующих вершин?Поскольку любой алгоритм решения задачи ИГ представляет собой проверку равенстванекоторых инвариантных относительно изоморфизма количественных характеристикграфов, неясный статус задачи ИГ в иерархии теории сложности непосредственносвязан с вопросом сложности вычисления полного инварианта графа. На данныймомент не доказано, что задача ИГ является NP-полной, равно как и не найденополиномиальных алгоритмов решения общего случая задачи.Единственным известным полным инвариантом графа является его каноническийкод - максимальное число, двоичная запись которого может быть получена путемнекоторой конкатенации строк верхне-(нижне-)треугольной подматрицы матрицысмежности графа [1].Полные инварианты известны лишь для немногих относительно простых классовграфов, поскольку наличие полиномиально вычислимого полного инварианта для графовиз некоторого класса эквивалентно полиномиальной разрешимости задачи ИГ дляграфов из этого класса. Так, в работе [2] представлен полный инвариант для деревьеви в целом класса ациклических графов, в работе [3] -для планарных графов. Однаков этих работах, как и в большинстве работ, нацеленных на нахождение полногоинварианта для ограниченного класса графов, полный инвариант ищется как результатканонизации графа - процесс, который может быть описан следующим образом.Пусть G - некоторый класс графов. Пусть f : G ^ {0,1}* -функция, отображающаяграф в пространство битовых строк (канонических кодов), такая, что для всехG, H E G имеем G ~ H ^ f (G) = f (H), то есть f - полный инвариант для графовиз G. Если f дает для G граф f (G) такой, что G ~ f (G), то f (G) -канонический кодграфа, по которому восстанавливается сам граф.В этой работе предлагается алгебраический полный инвариант ациклических графов,который не получается в результате канонизации графа, а представляет собоймножество из 1 + n(n + 1)/2 числовыхзначений, каждое из которых есть произведение собственных значений из спектра графа и спектров его подграфов. Этот подходпозволяет рассмотреть вопрос поиска полного инварианта для классов графов, используяалгебраические свойства матриц, представляющих графы, и допускает обобщенияна более широкие классы графов. Вариант такого обобщения также рассматриваетсяв работе.

Скачать электронную версию публикации