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

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

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

Это сообщение отредактировал(а) mrgloom - 7.2.2013, 11:37

дай определение "похожего" графа

ну самое простое например у нас модель граф 3 вершины равносторонний треугольник и мы в большом графе ищем подграф из 3 вершин который похож на равносторонний треугольник как метрику можно использовать разницу между ребрами и находить не точное совпадение, а по порогу.
+ еще хотелось бы чтобы можно было находить вне зависимость от масштаба.
А описательный вектор у вершины мы используем как доп. критерий, например если вектор состоит из 1 элемента(на примере цвета) у нашего треугольника вершины красный, синий, белый значит нам не подходит треугольник такого же размера, но у которого все вершины черные.
Если признак вектор большой размерности можно опять же по евклидовой метрике или махаланобиса сравнивать и так же отсекать по порогу.

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