Задача пошуку ізоморфного підграфа

Матеріал з 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.

Задача пошуку ізоморфного підграфа є узагальненням задачі про ізоморфізм графів, у якій запитується, чи граф граф G ізоморфний графу H — відповідь для задачі про ізоморфізм графів «так» тоді й лише тоді, коли графи G і H мають однакове число вершин і ребер та задача пошуку ізоморфного підграфа для графів G та H дає «так». Проте статус задачі ізоморфізму графів з погляду теорії складності залишається відкритим.

ГрегерШаблон:Sfn показав, що якщо виконано Шаблон:Нппро Шаблон:Не перекладено монотонних властивостей графа, то будь-яка задача пошуку ізоморфного підграфа має складність запиту Ω(n3/2). Тобто розв'язання задачі пошуку ізоморфного підграфа вимагає перевірки існування або відсутності у вході Ω(n3/2) різних ребер графа[2].

Алгоритми

УльманШаблон:Sfn описав рекурсивну процедуру із поверненням для розв'язання задачі пошуку ізоморфного підграфа. Хоча час роботи цього алгоритму, в загальному випадку, експоненційний, він працює за поліноміальний час для будь-якого фіксованого H (тобто час роботи обмежено поліномом, який залежить від вибору H). Якщо G — планарний граф (або, загальніше, граф із обмеженим розширенням), а H — фіксований, час розв'язання задачі пошуку ізоморфного підграфа можна скоротити до лінійного часуШаблон:SfnШаблон:Sfn.

2010 року УльманШаблон:Sfn суттєво оновив алгоритм зі статті 1976 року.

Застосування

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

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

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

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

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

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