1

Тема: найти похожие подграфы

Допустим есть 2 графа имеющие разное кол-во вершин(на самом деле вершина это точка в 2D), у рёбер есть веса- евклидово расстояние между точками, у вершин есть некий описательный вектор их характеризующий.
Необходимо найти похожие подграфы внутри этих графов.

Вторая задача:
Есть малый подграф(модель) надо найти в большом графе похожий на модель подграф.

Как можно решить такие задачи?

2

Re: найти похожие подграфы

Может, не пытаться уходить от геометрической задачи к абстрактной графовой задаче? Скажем, как-то так: перебирать все тройки вершин в первом графе и во втором графе - тем самым мы зафиксировали некоторое "приложение" одного графа к другому, а дальше выбрать те пары вершин из первого множества и из второго множества, которые оказались близки.

3

Re: найти похожие подграфы

если мы перебрали все тройки вершин из 2-х графов на предмет похожести это значит мы нашли подграфы из 3 вершин ,а никакого "приложения" там быть не может, т.к. 2 графа это как бы 2 сцены и мы хотим найти в них модели-паттерны которые похожи.
по идее мы можем и в 1 графе искать такие похожие модели.


вот тут еще нечто похожее
http://habrahabr.ru/post/154975/