Максимальный общий индуцированный подграф
В теории графов и теоретической информатике максимальный общий индуцированный подграф двух графов G и H — это граф, который является индуцированным подграфом как G так и H. , и это имеет как можно больше вершин.
Найти этот граф NP-трудно .В соответствующей задаче решения входными данными являются два графа G и H и число k . Проблема состоит в том, чтобы решить, имеют ли G и H общий индуцированный подграф по крайней мере с k вершинами. Эта задача является NP-полной . [1] Это обобщение проблемы изоморфизма индуцированного подграфа , которая возникает, когда k равно числу вершин в меньшем из G и H , так что весь этот граф должен появиться как индуцированный подграф другого графа.
Судя по трудностям аппроксимации задачи о максимальном независимом множестве , задачу о максимальном общем индуцированном подграфе также трудно аппроксимировать. [2] Это означает, что, если только P = NP , не существует алгоритма аппроксимации , который за полиномиальное время на -вершинные графы, всегда находит решение с точностью до коэффициента оптимального для любого . [3]
решений этой проблемы является построение модульного графа произведений G возможных и H. Одним из В этом графе наибольшая клика соответствует максимальному общему индуцированному G и H. подграфу Следовательно, алгоритмы поиска максимальных клик можно использовать для поиска максимального общего индуцированного подграфа. [4] Более того, модифицированный алгоритм максимальной клики можно использовать для поиска максимального общего связного подграфа. [5]
Алгоритм McSplit (вместе с его вариантом McSplit↓) представляет собой алгоритм прямой проверки , который не использует кликовое кодирование, но использует компактную структуру данных для отслеживания вершин в графе H , с которыми каждая вершина в графе G. может быть сопоставлена Обе версии алгоритма McSplit превосходят кликовое кодирование для многих классов графов. [6] Более эффективная реализация McSplit — McSplitDAL+PR, которая сочетает в себе агент обучения с подкреплением и некоторые эвристические оценки, вычисляемые с помощью алгоритма PageRank . [7]
Приложения
[ редактировать ]Алгоритмы максимального общего индуцированного подграфа составляют основу как для различения графов, так и для выравнивания графов. Разность графов идентифицирует и подчеркивает различия между двумя графиками путем точного определения изменений, дополнений или удалений. Выравнивание графов включает в себя поиск соответствий между вершинами и ребрами двух графов для выявления схожих структур.
Алгоритмы максимального общего индуцированного подграфа имеют давнюю традицию в биоинформатике , хемоинформатике , [8] [9] фармакофорное картирование , [10] распознавание образов , [11] компьютерное зрение , анализ кода, компиляторы и проверка моделей .
Эта проблема также особенно полезна в разработке программного обеспечения и системной инженерии на основе моделей , где программный код и инженерные модели (например, Simulink , UML-диаграммы ) представлены в виде графовых структур данных. Разность графов можно использовать для обнаружения изменений между различными версиями программного кода и моделями для аудита изменений, отладки, контроля версий и совместной командной разработки.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Майкл Р. Гари и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 А1.4: GT48, стр. 202.
- ^ Канн, Вигго (1992), «Об аппроксимируемости проблемы максимального общего подграфа», STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики Кашан, Франция, 13–15 февраля 1992 г., Труды , Конспекты лекций по информатике, том. 577, Springer Science $\mathplus$ Business Media, стр. 375–388, doi : 10.1007/3-540-55210-3_198 , ISBN 978-3-540-55210-9 .
- ^ Цукерман, Д. (2006), «Экстракторы линейных степеней и неаппроксимируемость максимальной клики и хроматического числа», Proc. 38-й симпозиум ACM. Теория вычислений , стр. 681–690, doi : 10.1145/1132516.1132612 , ISBN. 1-59593-134-1 , S2CID 5713815 , ECCC TR05-100 .
- ^ Барроу, Х.; Берстолл, Р. (1976), «Изоморфизм подграфов, сопоставление реляционных структур и максимальных клик», Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190(76)90049-1 .
- ^ МакКриш, Кьяран; Ндиайе, Самба Ндодж; Проссер, Патрик; Солнон, Кристина (2016), «Модели клики и ограничений для задач максимального общего (связного) подграфа» (PDF) , Принципы и практика программирования с ограничениями - 22-я Международная конференция, CP 2016, Тулуза, Франция, 5-9 сентября 2016 г., Труды , Конспекты лекций по информатике, вып. 9892, Springer International Publishing, стр. 350–368, doi : 10.1007/978-3-319-44953-1_23 , ISBN. 978-3-319-44952-4 , S2CID 215812381
- ^ МакКриш, Кьяран; Проссер, Патрик; Тримбл, Джеймс (2017), «Алгоритм разделения для задач максимального общего подграфа», Труды двадцать шестой международной совместной конференции по искусственному интеллекту, {IJCAI} 2017, Мельбурн, Австралия, 19–25 августа 2017 г. , ijcai.org , стр. 712–719, doi : 10.24963/ijcai.2017/99 , ISBN. 9780999241103
- ^ Калабрезе, Андреа; Кардоне, Лоренцо; Ликата, Сальваторе; Порро, Марко; Кер, Стефано (2023). Алгоритм парсинга веб-страниц для улучшения вычисления максимального общего подграфа . SCITEPRESS - Публикации по науке и технологиям. стр. 197–206. дои : 10.5220/0012130800003538 . ISBN 978-989-758-665-1 .
- ^ Шитгат, Леандер; Рамон, Ян; Брюйнуг, Морис (1 декабря 2013 г.). «Алгоритм максимального общего подграфа с полиномиальным временем для внешнепланарных графов и его применение к хемоинформатике» . Анналы математики и искусственного интеллекта . 69 (4): 343–376. дои : 10.1007/s10472-013-9335-0 . ISSN 1573-7470 .
- ^ Эрлих, Ганс-Кристиан; Рэри, Матиас (2011). «Алгоритмы изоморфизма максимального общего подграфа и их приложения в молекулярной науке: обзор» . WIREs Вычислительная молекулярная наука . 1 (1): 68–79. дои : 10.1002/wcms.5 . ISSN 1759-0876 .
- ^ Раймонд, Джон В.; Уиллетт, Питер (2002), «Алгоритмы изоморфизма максимального общего подграфа для сопоставления химических структур» (PDF) , Journal of Computer-Aided Molecular Design , 16 (7): 521–533, Bibcode : 2002JCAMD..16..521R , doi : 10.1023/A:1021271615909 , PMID 12510884 , S2CID 5202419 .
- ^ Конте, Д.; Фоджа, П.; Сансоне, К.; Венто, М. (2004). «ТРИДЦАТЬ ЛЕТ СООТВЕТСТВИЯ ГРАФОВ В РАСПОЗНАВАНИЕ ОБРАЗОВ» . Международный журнал распознавания образов и искусственного интеллекта . 18 (03): 265–298. дои : 10.1142/S0218001404003228 . ISSN 0218-0014 .