Модульное произведение графов

В теории графов модульное произведение графов представляет собой $G$ и $H$ граф, образованный объединением $G$ и $H$ , который имеет приложения к изоморфизму подграфов .Это один из нескольких различных типов графовых произведений , которые были изучены, обычно с использованием одного и того же набора вершин ( декартово произведение наборов вершин двух графов $G$ и $H$ ), но с разными правилами определения того, какие ребра включать.

Определение

Множество вершин модульного произведения $G$ и $H$ является декартовым произведением $V (G)\times V (H)$ .Любые две вершины $(u, v)$ и $(u', v')$ смежны в модульном произведении $G$ и $H$ , еслии только если $u$ отличен от $u'$ , $v$ отличен от $v'$ и либо

$u$ соседствует с $u'$ , а $v$ соседствует с $v'$ , или
$u$ не соседствует с $u'$ , а $v$ не соседствует с $v'$ .

Приложение к изоморфизму подграфов

графе модульного произведения соответствуют изоморфизмам индуцированных подграфов G $Клики в$ и $H$ . Следовательно, граф модульного произведения можно использовать для сведения проблем индуцированного изоморфизма подграфов к проблемам поиска клик в графах. В частности, максимальный общий индуцированный подграф G $H$ и $в$ соответствует максимальной клике их модульном произведении. Хотя проблемы поиска наибольших общих индуцированных подграфов и поиска максимальных клик являются NP-полными , это сокращение позволяет алгоритмы поиска клик применять к проблеме общего подграфа.

Ссылки

Барроу, Х.; Берстолл, Р. (1976), «Изоморфизм подграфов, сопоставление реляционных структур и максимальных клик», Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190(76)90049-1 .
Леви, Г. (1973), «Заметка о выводе максимальных общих подграфов двух ориентированных или неориентированных графов», Calcolo , 9 (4): 341–352, doi : 10.1007/BF02575586 .
Визинг В.Г. (1974), "Редукция проблемы изоморфизма и изоморфного входа к задаче нахождения неплотности графа", Тр. 3-я Всесоюзная конф. Проблемы теоретической кибернетики , с. 124 .