Субографиялық изоморфизм мәселесі - Subgraph isomorphism problem - Wikipedia

Жылы теориялық информатика, субографиялық изоморфизм проблема - бұл екі болатын есептік тапсырма графиктер G және H енгізу ретінде беріледі, ал біреуін анықтау керек G құрамында а подограф Бұл изоморфты дейін H.Субографиялық изоморфизм - бұл екеуін де жалпылау максималды проблема және графикте а бар-жоғын тексеру мәселесі Гамильтон циклі, және сондықтан NP аяқталды.[1] Алайда субографиялық изоморфизмнің кейбір басқа жағдайлары көпмүшелік уақытта шешілуі мүмкін.[2]

Кейде аты субографиялық сәйкестік сол проблема үшін де қолданылады. Бұл атау шешім қабылдау проблемасынан гөрі осындай субографияны табуға баса назар аударады.

Шешім мәселесі және есептеудің күрделілігі

Субрографиялық изоморфизмнің NP-толық екендігін дәлелдеу үшін оны а түрінде тұжырымдау керек шешім мәселесі. Шешім проблемасына кіріс сызбалар жұбы болып табылады G және H. Мәселенің жауабы оң болады H тармақшасына изоморфты болып табылады G, ал әйтпесе теріс.

Ресми сұрақ:

Келіңіздер , график болу Ішкі сызба бар ма? осындай ? I. e., Бар ма? биекция осындай ?

Субрографиялық изоморфизмнің NP толық екендігінің дәлелі қарапайым және төмендеуіне негізделген клика проблемасы, NP толық шешімі, онда кіріс бір график болады G және сан кдеген сұрақ туындайды G құрамында а толық ішкі сызба бірге к төбелер. Мұны субографиялық изоморфизм мәселесіне аудару үшін жай ғана рұқсат етіңіз H толық граф Қк; онда субографиялық изоморфизм мәселесінің жауабы G және H үшін кликалық есептің жауабына тең G және к. Клик проблемасы NP-мен аяқталғандықтан, бұл көпмүшелік уақытты бір рет азайту субографиялық изоморфизмнің де NP-аяқталғандығын көрсетеді.[3]

-Дан балама қысқарту Гамильтон циклі мәселе графикті аударады G бұл графикалық жұпта Гамильтондылыққа тексерілуі керек G және H, қайда H - бұл бірдей шыңдар саны бар цикл G. Гамильтон циклінің проблемасы NP-ге толығымен байланысты жазықтық графиктер, бұл субографиялық изоморфизм жазықтық жағдайда да NP-толық болып қала беретіндігін көрсетеді.[4]

Субографиялық изоморфизм - бұл жалпылау графикалық изоморфизм мәселесі, бұл сұрайды G изоморфты болып табылады H: егер изоморфизм графигінің жауабы дұрыс болса және егер болса G және H екеуінде де шыңдар мен шеттердің сандары және субографиялық изоморфизм мәселесі бірдей G және H шындық Алайда графикалық изоморфизмнің күрделілігі-теоретикалық мәртебесі ашық сұрақ болып қала береді.

Контекстінде Аандераа-Карп-Розенберг болжамдары үстінде сұраныстың күрделілігі монотонды графиктің қасиеттері, Грёгер (1992) кез-келген субографиялық изоморфизм мәселесінің сұраныстың күрделілігі бар екенін көрсетті Ω (n3/2); яғни субграфиялық изоморфизмді шешу үшін Ω (кірісінде бар немесе жоқтығын тексеру алгоритмі қажет)n3/2) графиктің әр түрлі шеттері.[5]

Алгоритмдер

Ульман (1976) субографиялық изоморфизм мәселесін шешудің рекурсивті кері трекинг процедурасын сипаттайды. Оның жұмыс уақыты, жалпы алғанда, экспоненциалды болғанымен, кез келген тіркелген таңдау үшін көпмүшелік уақытты алады H (таңдауына байланысты көпмүшелікпен H). Қашан G Бұл жазықтық график (немесе жалпы график шектелген кеңею ) және H бекітілген, субографиялық изоморфизмнің жұмыс істеу уақытын қысқартуға болады сызықтық уақыт.[2]

Ульман (2010) 1976 жылғы субографиялық изоморфизм алгоритмі қағазының айтарлықтай жаңаруы.

Корделла (2004) 2004 жылы Ульманнға негізделген VF2 басқа алгоритмі ұсынылды, ол әр түрлі эвристиканы қолдана отырып нақтылау процесін жақсартады және жадты едәуір аз қолданады.

Бонничи (2013) ең жақсы алгоритм ұсынды, ол кейбір эвристиканы қолдана отырып, шыңдардың бастапқы тәртібін жақсартады.

Үлкен графиктер үшін заманауи алгоритмдерге CFL-Match және Turboiso және оның DAF сияқты кеңейтімдері кіреді. Хан (2019).

Қолданбалар

Субографиялық изоморфизм аймағында қолданылған химинформатика олардың құрылымдық формуласынан химиялық қосылыстардың ұқсастығын табу; бұл салада жиі термин қолданылады ішкі құрылымды іздеу қолданылады.[6] Сұраныс құрылымы көбінесе a көмегімен графикалық түрде анықталады құрылым редакторы бағдарлама; КҮЛІМДЕР деректер базасына негізделген жүйелер әдетте сұраныстардың көмегімен анықтайды SMARTS, а КҮЛІМДЕР кеңейту.

Графиктің изоморфты көшірмелерін санаудың тығыз байланысты мәселесі H үлкенірек графикте G деректер базасында үлгіні табуға қолданылды,[7] The биоинформатика ақуыз-ақуыздың өзара әрекеттесу желілері,[8] және экспоненциалды кездейсоқ график математикалық модельдеу әдістері әлеуметтік желілер.[9]

Ольрич және басқалар. (1993) ішіндегі субографиялық изоморфизмнің қолданылуын сипаттаңыз компьютерлік дизайн туралы электрондық тізбектер. Субографты сәйкестендіру сонымен қатар графикті қайта жазу (ең көп жұмыс уақытын қажет етеді), осылайша ұсынылады графикалық қайта жазу құралдары.

Мәселе сонымен қатар қызығушылық тудырады жасанды интеллект, онда ол массивтің бөлігі болып саналады үлгілерді сәйкестендіру есептерде; ретінде белгілі субографиялық изоморфизмнің кеңеюі графикалық тау-кен сол салаға қызығушылық танытады.[10]

Сондай-ақ қараңыз

Ескертулер

  1. ^ Түпнұсқа Кук (1971) дәлелдейтін қағаз Кук-Левин теоремасы -дан төмендетуді қолдана отырып, субрографиялық изоморфизмді NP-толық деп көрсетті 3-SAT кликтер қатысады.
  2. ^ а б Эппштейн (1999); Нешетил және Оссона де Мендес (2012)
  3. ^ Вегенер, Инго (2005), Күрделілік теориясы: тиімді алгоритмдердің шектерін зерттеу, Springer, б. 81, ISBN  9783540210450.
  4. ^ де ла Хигуера, Колин; Джанодет, Жан-Кристоф; Сэмюэль, Эмили; Дамианд, Гийом; Солнон, Кристин (2013), «Ашық жазықтық графигі мен субографиялық изоморфизмнің полиномдық алгоритмдері» (PDF), Теориялық информатика, 498: 76–99, дои:10.1016 / j.tcs.2013.05.026, МЫРЗА  3083515, 70-ші жылдардың ортасынан бастап изоморфизм есебі жазықтық графиктер үшін көпмүшелік уақытта шешілетіні белгілі болды. Сонымен қатар, субизоморфизм мәселесі әлі де N P-толық, атап айтқанда, Гамильтон циклінің мәселесі планарлы графиктер үшін NP-толық болғандығы атап өтілді.
  5. ^ Мұнда. Шақырады Үлкен Омега жазбасы.
  6. ^ Ульман (1976)
  7. ^ Курамочи және Карыпис (2001).
  8. ^ Pržulj, Corneil & Jurisica (2006).
  9. ^ Снейдерс және басқалар. (2006).
  10. ^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; кеңейтілген нұсқасы https://e-reports-ext.llnl.gov/pdf/332302.pdf

Әдебиеттер тізімі