Аннотация:В работе исследуется задача поиска подграфов в базе данных графов. Причем графы рассматриваются неотмеченные. Классический алгоритм подразумевает полный перебор элементов базы данных, с последующим запуском алгоритма поиска подграфа в графе, что уже само по себе является экспоненциально сложной задачей относительно числа ребер в графе.
Автором предлагается 2 способа ускорения алгоритма поиска. Первый – организация предварительной фильтрации элементов базы данных с помощью алгоритма полиномиальной сложности. Этот подход был ранее описан в литературе для случая отмеченных графов, и адаптирован автором для случая неотмеченных графов.
Второй способ ускорения поиска заключается в предварительном подсчете характеристик графов из базы данных для более быстрой последующей фильтрации. Для каждого из графов из базы данных строится специальное дерево частично-упорядоченных путей графа, которое потом в процессе фильтрации комбинируется с аналогичным деревом для графа-запроса, что позволяет быстро отфильтровать неподходящие графы.