Нежное введение в изоморфизм графов для ограниченных валансных графов

17

Я читал о классах графов , для которых Изоморфизм графов ( ) находится в P . Одним из таких случаев являются графы ограниченной валентности (максимально над степенью каждой вершины), как описано здесь . Но я нашел это слишком абстрактным. Я был бы благодарен, если бы кто-нибудь мог предложить мне несколько ссылок пояснительного характера. У меня нет сильного опыта в теории групп, поэтому я бы предпочел статьи, в которых теория групп нежно используется (мой опыт в CS).GIP

DurgaDatta
источник
1
У меня нет книги (к сожалению), но проблема изоморфизма графов: ее структурная сложность Йоханнеса Коблера, Уве Шенинга и Якобо Торана может содержать доказательство для случая ограниченной степени. Вы можете проверить это.
Цуёси Ито
2
@TsuyoshiIto: Хотя это отличная книга, которая дает хорошее представление о GI и о значительной общей структурной сложности, она не содержит много (если вообще что-то) о случае ограниченной степени. Я не знаю мягкого введения в случай ограниченной степени, но оно настолько тесно связано с теоретико-групповыми методами, что я сомневаюсь, что существует экспозиция, которая использует теорию групп «только осторожно» (как того требует ОП).
Джошуа Грохов
Я хотел бы дать обзор, я сделаю это в ближайшее время!
Джим

Ответы:

14

Алгоритм изоморфизма графа ограниченной степени настолько тесно связан с (перестановочной) теорией групп, что я сомневаюсь, что есть введение, которое использует группы «лишь осторожно». Однако вы можете обратиться к доктору Паоло Коденотти. тезис для более полной предыстории. Он не охватывает точно изоморфизм графа ограниченной степени, но охватывает инструменты, необходимые для этого (а остальная часть тезиса посвящена гиперграфам ограниченного ранга, расширяя самый известный алгоритм общего изоморфизма графа для случая гиперграфа ограниченного ранга) ,

Вы также можете найти книгу « Теоретико-групповые алгоритмы и изоморфизм графов» полезной, поскольку она охватывает большую часть необходимого фона (глава 2, «Основные понятия», составляет 47 страниц) и представляет собой гораздо более неторопливую экспозицию, чем большинство опубликованных работ по тема.

Джошуа Грохов
источник
1

Обозначения: Пусть будет граф, е = ( v 1 , v 2 ) ребро X . Множество вершин V K множество вершин расстояния к от е , и пусть ч будет высота X .X=(V,E)e=(v1,v2)XVkkehX

Согласно определению , V = V 0V 1V h и V ( h + 1 ) = . Пусть подмножество E k ребер X ( 0 k h ) определяется какVkV=V0V1VhV(h+1)=EkX(0kh)

Ek={(u,w)|uVk,wVkV(k+1)}.

Подграф определяется какXi

Xk=(V0V1Vk,E0E1E(k1)}

Например, X2={(V0V1V2,E0E1)}

- группа автоморфизмов графа X, где e фиксировано. Если B является порождающим множество A ¯u т е ( Х к ) , мы пишемB = у т е ( Х к ) , например, очевидночто у т е ( Х 0 ) = ( v 1 , v 2Aute(X)XeBAute(Xk)B=Aute(Xk) , Где ( v 1 , v 2 ) есть перестановка вершин v 1 , V 2 из X .Aute(X0)=(v1,v2)(v1,v2)v1,v2X

Принцип Построение порождающего множества группы автоморфизмов является полной задачей GI (изоморфизма графов) [1]. Таким образом, если мы можем вычислить порождающее множество группы автоморфизмов X (имеющей ограниченную валентность за полиномиальное время), мы можем решить GI за полиномиальное время. Итак, мы хотим определить A u t e ( X ) .XXAute(X)

Техника:

Построим . Для каждого X k построим A u t e ( X ( k ) )X0,X1.....XhXkAute(X(k))

Отметим, что перестановка может быть продолжена до автоморфизма A u t e ( X ( k + 1 ) ) .Aute(X(k))Aute(X(k+1))

Таким образом, генераторы могут быть получены из генераторов для A u t e ( X k ) .Aute(X(k+1))Aute(Xk)

Для построения генератора структурным типом манипулируют. Структурный тип E k можно разделить на конечные классы. Например, в трехвалентном случае существует только шесть типов (только пять из этих случаев действительно могут иметь место).EkEk

Мы будем классифицировать ребра в на типы и сгруппировать их в семейства. Это помогает создать ряд уникальных ярлыков.Ek

Aute(X(k))Aute(X(k))Aute(X(k+1))Aute(X)

Джим
источник
[1] Матон, Рудольф. , Замечание о проблеме подсчета изоморфизмов графов, Информ. Процесс. Lett. 8 (1979), нет. 3, 131–132.
Джим