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

Иногда также используется название сопоставление подграфа для той же задачи. Это название делает упор на поиске таких подграфов, а не просто на разрешимости.

Задача разрешимости и вычислительная сложность

Для доказательства, что задача поиска изоморфного подграфа NP-полна, её нужно сформулировать как задачу разрешимости . Входом задачи разрешимости служит пара графов G и H . Ответ задачи положителен, если H изоморфен некоторому подграфу графа G , и отрицателен в ином случае.

Формальное задание:

Пусть ${\displaystyle G=(V,E)}$ , ${\displaystyle H=(V^{\prime },E^{\prime })}$ — два графа. Существует ли подграф ${\displaystyle G_{0}=(V_{0},E_{0}):V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})}$ , такой, что ${\displaystyle G_{0}\cong H}$ ? Т.е. существует ли отображение ${\displaystyle f\colon V_{0}\rightarrow V^{\prime }}$ , такое, что ${\displaystyle (v_{1},v_{2})\in E_{0}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E^{\prime }}$ ?

Доказательство NP-полноты задачи поиска изоморфного подграфа просто и основывается на сведении к этой задаче задачи о клике , NP-полной задачи разрешимости, в которой входом служит один граф G и число k , а вопрос состоит в следующем: содержит ли граф G полный подграф с k вершинами. Для сведения этой задачи к задаче поиска изоморфного подграфа, просто возьмём в качестве графа H полный граф K _k . Тогда ответ для задачи поиска изоморфного подграфа с входными графами G и H равен ответу для задачи о клике для графа G и числа k . Поскольку задача о клике NP-полна, такая полиномиальная сводимость показывает, что задача поиска изоморфного подграфа также NP-полна .

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

Задача поиска изоморфного подграфа является обобщением , которая спрашивает, изоморфен ли граф G графу H — ответ для задачи об изоморфизме графов «да» тогда и только тогда, когда графы G и H имеют одно и то же число вершин и рёбер и задача поиска изоморфного подграфа для графов G и H даёт «да». Однако статус задачи изоморфизма графов с точки зрения теории сложности остаётся открытым.

Грёгер показал, что если выполнена гипотеза Аандераа — Карпа — Розенберга о монотонных свойств графа, то любая задача поиска изоморфного подграфа имеет сложность запроса Ω( n ^3/2 ). То есть решение задачи поиска изоморфного подграфа требует проверки существования или отсутствия во входе Ω( n ^3/2 ) различных рёбер графа .

Алгоритмы

Ульман описал рекурсивную процедуру с возвратом для решения задачи поиска изоморфного подграфа. Хотя время работы этого алгоритма, в общем случае, экспоненционально, он работает за полиномиальное время для любого фиксированного H (то есть время работы ограничено полиномом, зависящим от выбора H ). Если G является планарным графом (или, более обще, ), а H фиксирован, время решения задачи поиска изоморфного подграфа может быть сокращено до линейного времени .

Ульман существенно обновил алгоритм из статьи 1976-го года.

Приложения

Задача поиска изоморфного подграфа была применена в области хемоинформатики для поиска похожести химических соединений по их структурным формулам. Часто в этой области используется термин подструктурный поиск . Структура запроса часто определяется графически с использованием структурного редактора . Основанные на SMILES базы данных обычно определяют запросы с использованием , расширения SMILES .

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

Ольрих, Эбелинг, Гитинг и Сатер описали приложение задачи поиска изоморфного подграфа в cистеме автоматизированного проектирования электронных схем . Задача сопоставления подграфа является также подшагом при преобразовании графа (требующего наибольшего времени выполнения), а потому предоставляется инструментальными средствами преобразования графа.

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

Примечания

Литература