www.wikidata.uk-ua.nina.az

Задача пошуку ізоморфного підграфа обчислювальна задача в якій входом є два графи G displaystyle G і H displaystyle H і

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

Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час.

Задача розв'язності та обчислювальна складність ред.

Для доведення, що задача пошуку ізоморфного підграфа NP-повна, її потрібно сформулювати як задачу розв'язності. Входом задачі розв'язності є пара графів і . Відповідь задачі ствердна, якщо ізоморфний деякому підграфу графа і заперенчна в іншому випадку.

Формальна задача: Нехай ,  — два графи. Чи існує підграф , такий, що ? Тобто, чи існує відображення , таке, що ?

Доведення NP-повноти задачі пошуку ізоморфного підграфа просте і ґрунтується на зведенні до цієї задачі задачі про кліку, NP-повної задачі розв'язності, в якій входом є один граф і число , а питання полягає таке: чи містить граф повний підграф із вершинами. Для зведення цієї задачі до пошуку ізоморфного підграфа, просто візьмемо як граф повний граф . Тоді відповідь задачі пошуку ізоморфного подграфа зі вхідними графами і дорівнює відповіді для задачі про кліку для графа і числа . Оскільки задача про кліку NP-повна, така поліноміальна звідність показує, що задача пошуку ізоморфного підграфа також NP-повна.

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

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

Грегер показав, що якщо виконано гіпотезу Аандераа — Карпа — Розенберга[ru]про складність запиту[en] монотонних властивостей графа, то будь-яка задача пошуку ізоморфного підграфа має складність запиту . Тобто розв'язання задачі пошуку ізоморфного підграфа вимагає перевірки існування або відсутності у вході різних ребер графа.

Алгоритми ред.

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

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

Застосування ред.

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

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

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

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

Примітки ред.

  1. В оригінальній статті Кука (Cook, 1971), яка містить доведення теореми Кука — Левіна, вже показано, що задача пошуку ізоморфного підграфа NP-повна, зведенням із задачі 3-SAT із використанням клік.
  2. ↑ Eppstein, 1999, с. 1–27.
  3. ↑ Nešetřil, Ossona de Mendez, 2012, с. 400–401.
  4. Wegener, 2005, с. 81.
  5. de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013, с. 76–99.
  6. Gröger, 1992, с. 119–127.
  7. Тут Ω — омега велике.
  8. ↑ Ullmann, 1976, с. 31–42.
  9. Ullmann, 2010.
  10. Kuramochi, Karypis, 2001, с. 313.
  11. Pržulj, Corneil, Jurisica, 2006, с. 974–980.
  12. Snijders, Pattison, Robins, Handcock, 2006, с. 99–153.
  13. Ohlrich, Ebeling, Ginting, Sather, 1993, с. 31–37.
  14. http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf [ 2017-08-29 у Wayback Machine.]; розширена версія на https://e-reports-ext.llnl.gov/pdf/332302.pdf Архівна копія на сайті Wayback Machine.

Література ред.

  • S. A. Cook. Proc. 3rd ACM Symposium on Theory of Computing. — 1971. — DOI:10.1145/800157.805047.
  • Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Guillaume Damiand, Christine Solnon. Polynomial algorithms for open plane graph and subgraph isomorphisms // Theoretical Computer Science. — 2013. — Т. 498. — DOI:10.1016/j.tcs.2013.05.026. Від середини 1970-х відомо, що задачу пошуку ізоморфного підграфа для планарних графів можна розв'язати за поліноміальний час. Однак, було помічено, що задача пошуку підізоморфізму залишається NP-повною, зокрема, оскільки задача про гамільтонів цикл для планарних графів є NP-повною.
  • Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. — Springer, 2005. — ISBN 9783540210450.
  • David Eppstein. Subgraph isomorphism in planar graphs and related problems // Journal of Graph Algorithms and Applications. — 1999. — Т. 3, вип. 3. — arXiv:cs.DS/9911003. — DOI:10.7155/jgaa.00014.
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5.. A1.4: GT48, стр.202.
  • Hans Dietmar Gröger. On the randomized complexity of monotone graph properties // Acta Cybernetica. — 1992. — Т. 10, вип. 3. з джерела 24 вересня 2015..
  • Michihiro Kuramochi, George Karypis. 1st IEEE International Conference on Data Mining. — 2001. — ISBN 0-7695-1119-8. — DOI:10.1109/ICDM.2001.989534..
  • Miles Ohlrich, Carl Ebeling, Eka Ginting, Lisa Sather. Proceedings of the 30th international Design Automation Conference. — 1993. — ISBN 0-89791-577-1. — DOI:10.1145/157485.164556.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics) — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4..
  • N. Pržulj, D. G. Corneil, I. Jurisica. Efficient estimation of graphlet frequency distributions in protein–protein interaction networks // Bioinformatics. — 2006. — Т. 22, вип. 8. — DOI:10.1093/bioinformatics/btl030. — PMID:16452112.
  • T. A. B. Snijders, P. E. Pattison, G. Robins, M. S. Handcock. New specifications for exponential random graph models // Sociological Methodology. — 2006. — Т. 36, вип. 1. — DOI:10.1111/j.1467-9531.2006.00176.x.
  • Julian R. Ullmann. An algorithm for subgraph isomorphism // Journal of the ACM. — 1976. — Т. 23, вип. 1. — DOI:10.1145/321921.321925.
  • Hasan Jamil. 26th ACM Symposium on Applied Computing. — 2011. — С. 1058–1063..
  • Julian R. Ullmann. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism // Journal of Experimental Algorithmics. — 2010. — Т. 15. — DOI:10.1145/1671970.1921702.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Zadacha poshuku izomorfnogo pidgrafa obchislyuvalna zadacha v yakij vhodom ye dva grafi G displaystyle G i H displaystyle H i potribno viznachiti chi mistit G displaystyle G pidgraf izomorfnij grafu H displaystyle H Zadacha ye uzagalnennyam yak zadachi pro najbilshu kliku tak i zadachi pro perevirku chi mistit graf gamiltoniv cikl tomu ye NP povnoyu 1 Prote z deyakimi vidami pidgrafiv zadachu poshuku izomorfnogo pidgrafa mozhna rozv yazati za polinomialnij chas 2 3 Zmist 1 Zadacha rozv yaznosti ta obchislyuvalna skladnist 2 Algoritmi 3 Zastosuvannya 4 Primitki 5 LiteraturaZadacha rozv yaznosti ta obchislyuvalna skladnist red Dlya dovedennya sho zadacha poshuku izomorfnogo pidgrafa NP povna yiyi potribno sformulyuvati yak zadachu rozv yaznosti Vhodom zadachi rozv yaznosti ye para grafiv G displaystyle G nbsp i H displaystyle H nbsp Vidpovid zadachi stverdna yaksho H displaystyle H nbsp izomorfnij deyakomu pidgrafu grafa G displaystyle G nbsp i zaperenchna v inshomu vipadku Formalna zadacha Nehaj G V E displaystyle G V E nbsp H V E displaystyle H V prime E prime nbsp dva grafi Chi isnuye pidgraf G 0 V 0 E 0 V 0 V E 0 E V 0 V 0 displaystyle G 0 V 0 E 0 V 0 subseteq V E 0 subseteq E cap V 0 times V 0 nbsp takij sho G 0 H displaystyle G 0 cong H nbsp Tobto chi isnuye vidobrazhennya f V 0 V displaystyle f colon V 0 rightarrow V prime nbsp take sho v 1 v 2 E 0 f v 1 f v 2 E displaystyle v 1 v 2 in E 0 Leftrightarrow f v 1 f v 2 in E prime nbsp Dovedennya NP povnoti zadachi poshuku izomorfnogo pidgrafa proste i gruntuyetsya na zvedenni do ciyeyi zadachi zadachi pro kliku NP povnoyi zadachi rozv yaznosti v yakij vhodom ye odin graf G displaystyle G nbsp i chislo k displaystyle k nbsp a pitannya polyagaye take chi mistit graf G displaystyle G nbsp povnij pidgraf iz k displaystyle k nbsp vershinami Dlya zvedennya ciyeyi zadachi do poshuku izomorfnogo pidgrafa prosto vizmemo yak graf H displaystyle H nbsp povnij graf K k displaystyle K k nbsp Todi vidpovid zadachi poshuku izomorfnogo podgrafa zi vhidnimi grafami G displaystyle G nbsp i H displaystyle H nbsp dorivnyuye vidpovidi dlya zadachi pro kliku dlya grafa G displaystyle G nbsp i chisla k displaystyle k nbsp Oskilki zadacha pro kliku NP povna taka polinomialna zvidnist pokazuye sho zadacha poshuku izomorfnogo pidgrafa takozh NP povna 4 Alternativne zvedennya zadachi pro gamiltoniv cikl vidobrazhaye graf G displaystyle G nbsp yakij pereviryayetsya na gamiltonovist na paru grafiv G displaystyle G nbsp i H displaystyle H nbsp de H displaystyle H nbsp cikl sho maye take zh chislo vershin yak i G displaystyle G nbsp Oskilki zadacha pro gamiltoniv cikl ye NP povnoyu navit dlya planarnih grafiv to zadacha poshuku izomorfnogo pidgrafa takozh zalishayetsya NP povnoyu navit dlya planarnogo vipadku 5 Zadacha poshuku izomorfnogo pidgrafa ye uzagalnennyam zadachi pro izomorfizm grafiv u yakij zapituyetsya chi graf graf G displaystyle G nbsp izomorfnij grafu H displaystyle H nbsp vidpovid dlya zadachi pro izomorfizm grafiv tak todi j lishe todi koli grafi G displaystyle G nbsp i H displaystyle H nbsp mayut odnakove chislo vershin i reber ta zadacha poshuku izomorfnogo pidgrafa dlya grafiv G displaystyle G nbsp ta H displaystyle H nbsp daye tak Prote status zadachi izomorfizmu grafiv z poglyadu teoriyi skladnosti zalishayetsya vidkritim Greger 6 pokazav sho yaksho vikonano gipotezu Aanderaa Karpa Rozenberga ru pro skladnist zapitu en monotonnih vlastivostej grafa to bud yaka zadacha poshuku izomorfnogo pidgrafa maye skladnist zapitu W n 3 2 displaystyle Omega n 3 2 nbsp Tobto rozv yazannya zadachi poshuku izomorfnogo pidgrafa vimagaye perevirki isnuvannya abo vidsutnosti u vhodi W n 3 2 displaystyle Omega n 3 2 nbsp riznih reber grafa 7 Algoritmi red Ulman 8 opisav rekursivnu proceduru iz povernennyam dlya rozv yazannya zadachi poshuku izomorfnogo pidgrafa Hocha chas roboti cogo algoritmu v zagalnomu vipadku eksponencijnij vin pracyuye za polinomialnij chas dlya bud yakogo fiksovanogo H displaystyle H nbsp tobto chas roboti obmezheno polinomom yakij zalezhit vid viboru H displaystyle H nbsp Yaksho G displaystyle G nbsp planarnij graf abo zagalnishe graf iz obmezhenim rozshirennyam a H displaystyle H nbsp fiksovanij chas rozv yazannya zadachi poshuku izomorfnogo pidgrafa mozhna skorotiti do linijnogo chasu 2 3 2010 roku Ulman 9 suttyevo onoviv algoritm zi statti 1976 roku Zastosuvannya red Zadachu poshuku izomorfnogo podgrafa zastosovano v galuzi hemoinformatiki dlya poshuku shozhosti himichnih spoluk za yih strukturnimi formulami Chasto v cij galuzi vikoristovuyut termin pidstrukturnij poshuk 8 Struktura zapitu chasto viznachayetsya grafichno z vikoristannyam strukturnogo redaktora Zasnovani na SMILES bazi danih zazvichaj viznachayut zapiti z vikoristannyam SMARTS en rozshirennya SMILES Tisno pov yazani zadachi pidrahunku chisla izomorfnih kopij grafa H displaystyle H nbsp u bilshomu grafi G displaystyle G nbsp vikoristovuyutsya dlya viyavlennya shablonu v bazah danih 10 u bioinformatici vzayemodiyi proteyin proteyin 11 i v metodah eksponencijnih vipadkovih grafiv dlya matematichnogo modelyuvannya socialnih merezh 12 Olrih Ebeling Giting i Sater 13 opisali zatsosuvannya zadachi poshuku izomorfnogo pidgrafa v sistemi avtomatizovanogo proyektuvannya elektronnih shem Zadacha ye takozh pidkrokom pid chas peretvorennya grafa sho potrebuye najbilshogo chasu vikonannya tomu nadayetsya instrumentalnimi zasobami peretvorennya grafa Do zadachi takozh ye interes u galuzi shtuchnogo intelektu de yiyi vvazhayut chastinoyu grupi zavdan zistavlennya zi zrazkom u grafah Takozh u cij galuzi rozglyadayetsya rozshirennya zadachi poshuku izomorfnogo grafa vidome yak analiz grafa en 14 Primitki red V originalnij statti Kuka Cook 1971 yaka mistit dovedennya teoremi Kuka Levina vzhe pokazano sho zadacha poshuku izomorfnogo pidgrafa NP povna zvedennyam iz zadachi 3 SAT iz vikoristannyam klik a b Eppstein 1999 s 1 27 a b Nesetril Ossona de Mendez 2012 s 400 401 Wegener 2005 s 81 de la Higuera Janodet Samuel Damiand Solnon 2013 s 76 99 Groger 1992 s 119 127 Tut W omega velike a b Ullmann 1976 s 31 42 Ullmann 2010 Kuramochi Karypis 2001 s 313 Przulj Corneil Jurisica 2006 s 974 980 Snijders Pattison Robins Handcock 2006 s 99 153 Ohlrich Ebeling Ginting Sather 1993 s 31 37 http www aaai org Papers Symposia Fall 2006 FS 06 02 FS06 02 007 pdf Arhivovano 2017 08 29 u Wayback Machine rozshirena versiya na https e reports ext llnl gov pdf 332302 pdf Arhivna kopiya na sajti Wayback Machine Literatura red S A Cook Proc 3rd ACM Symposium on Theory of Computing 1971 DOI 10 1145 800157 805047 Colin de la Higuera Jean Christophe Janodet Emilie Samuel Guillaume Damiand Christine Solnon Polynomial algorithms for open plane graph and subgraph isomorphisms Theoretical Computer Science 2013 T 498 DOI 10 1016 j tcs 2013 05 026 Vid seredini 1970 h vidomo sho zadachu poshuku izomorfnogo pidgrafa dlya planarnih grafiv mozhna rozv yazati za polinomialnij chas Odnak bulo pomicheno sho zadacha poshuku pidizomorfizmu zalishayetsya NP povnoyu zokrema oskilki zadacha pro gamiltoniv cikl dlya planarnih grafiv ye NP povnoyu Ingo Wegener Complexity Theory Exploring the Limits of Efficient Algorithms Springer 2005 ISBN 9783540210450 David Eppstein Subgraph isomorphism in planar graphs and related problems Journal of Graph Algorithms and Applications 1999 T 3 vip 3 arXiv cs DS 9911003 DOI 10 7155 jgaa 00014 Michael R Garey David S Johnson Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman 1979 ISBN 0 7167 1045 5 A1 4 GT48 str 202 Hans Dietmar Groger On the randomized complexity of monotone graph properties Acta Cybernetica 1992 T 10 vip 3 Arhivovano z dzherela 24 veresnya 2015 Michihiro Kuramochi George Karypis 1st IEEE International Conference on Data Mining 2001 ISBN 0 7695 1119 8 DOI 10 1109 ICDM 2001 989534 Miles Ohlrich Carl Ebeling Eka Ginting Lisa Sather Proceedings of the 30th international Design Automation Conference 1993 ISBN 0 89791 577 1 DOI 10 1145 157485 164556 Jaroslav Nesetril Patrice Ossona de Mendez Sparsity Graphs Structures and Algorithms Springer 2012 T 28 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 N Przulj D G Corneil I Jurisica Efficient estimation of graphlet frequency distributions in protein protein interaction networks Bioinformatics 2006 T 22 vip 8 DOI 10 1093 bioinformatics btl030 PMID 16452112 T A B Snijders P E Pattison G Robins M S Handcock New specifications for exponential random graph models Sociological Methodology 2006 T 36 vip 1 DOI 10 1111 j 1467 9531 2006 00176 x Julian R Ullmann An algorithm for subgraph isomorphism Journal of the ACM 1976 T 23 vip 1 DOI 10 1145 321921 321925 Hasan Jamil 26th ACM Symposium on Applied Computing 2011 S 1058 1063 Julian R Ullmann Bit vector algorithms for binary constraint satisfaction and subgraph isomorphism Journal of Experimental Algorithmics 2010 T 15 DOI 10 1145 1671970 1921702 Otrimano z https uk wikipedia org w index php title Zadacha poshuku izomorfnogo pidgrafa amp oldid 40043244