Задача поиска изоморфного подграфа

Материал из testwiki
Перейти к навигации Перейти к поиску

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

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

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

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

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

Пусть G=(V,E), H=(V′,E′) — два графа. Существует ли подграф G0=(V0,E0):V0⊆V,E0⊆E∩(V0×V0), такой, что G0≅H? Т.е. существует ли отображение f:V0→V′, такое, что (v1,v2)∈E0⇔(f(v1),f(v2))∈E′?

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

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

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

ГрёгерШаблон:Sfn показал, что если выполнена гипотеза Аандераа — Карпа — Розенберга о Шаблон:Не переведено 5 монотонных свойств графа, то любая задача поиска изоморфного подграфа имеет сложность запроса Ω(n3/2). То есть решение задачи поиска изоморфного подграфа требует проверки существования или отсутствия во входе Ω(n3/2) различных рёбер графа[2].

Алгоритмы

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

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

Приложения

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

  1. ↑ В оригинальной статье Кука Шаблон:Harv, содержащей доказательство теоремы Кука — Левина, уже было показано, что задача поиска изоморфного подграфа NP-полна, путём сведения из задачи 3-SAT с использованием клик
  2. ↑ Здесь Ω — Омега большое.
  3. ↑ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf Шаблон:Wayback; expanded version at https://e-reports-ext.llnl.gov/pdf/332302.pdf Шаблон:Wayback
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Задача_поиска_изоморфного_подграфа&oldid=18362