Здравствуйте,
Есть сабжевая задача. Графы, с в которых предстоит поиск, с большой вероятностью могут быть "регуляризированными", т.е. состоять из нескольких одинаковых графов (связанных и не связанных). Есть идея реализовать функцию вроде IsRegular, которая определит регуляризован ли граф, выделит его минимальный составной подграф (т.е. тот, из которых состоит исходный граф), чтоб производить поиск подграфа на нем. Возможно ситуация, когда граф будет регулярен лишь частично, тогда наверное нужно как-то разграничивать регулярную и нерегулярную области?
Вопрос: куда копать? Насколько я понимаю, эта задача решается фракталами. Или нет? Кто нибудь сталкивался с такой задачей?

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

Здравствуйте, chocholl, Вы писали:

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

Здравствуйте, Valen, Вы писали:

V>Есть сабжевая задача. Графы, с в которых предстоит поиск, с большой вероятностью могут быть "регуляризированными", т.е. состоять из нескольких одинаковых графов (связанных и не связанных). Есть идея реализовать функцию вроде IsRegular, которая определит регуляризован ли граф, выделит его минимальный составной подграф (т.е. тот, из которых состоит исходный граф), чтоб производить поиск подграфа на нем. Возможно ситуация, когда граф будет регулярен лишь частично, тогда наверное нужно как-то разграничивать регулярную и нерегулярную области?


Не совсем понятно, в чем вопрос. Поиск подграфа — NP-полная задача, так что тут только перебор. Любая информация может быть использована для уменьшения этого перебора. Если граф регулярен, то можно, действительно, искать подграф только на одном кусочке. Только надо учесть, что если регулярные куски связаны, то подграф может входить в несколько кусков одновременно.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, Valen, Вы писали:

V>>Есть сабжевая задача. Графы, с в которых предстоит поиск, с большой вероятностью могут быть "регуляризированными", т.е. состоять из нескольких одинаковых графов (связанных и не связанных). Есть идея реализовать функцию вроде IsRegular, которая определит регуляризован ли граф, выделит его минимальный составной подграф (т.е. тот, из которых состоит исходный граф), чтоб производить поиск подграфа на нем. Возможно ситуация, когда граф будет регулярен лишь частично, тогда наверное нужно как-то разграничивать регулярную и нерегулярную области?


V_>Не совсем понятно, в чем вопрос. Поиск подграфа — NP-полная задача, так что тут только перебор. Любая информация может быть использована для уменьшения этого перебора. Если граф регулярен, то можно, действительно, искать подграф только на одном кусочке. Только надо учесть, что если регулярные куски связаны, то подграф может входить в несколько кусков одновременно.
Да, задача NP-полная и только полный перебор. Собственно я хотел спросить как выяснить, что граф (частично)регулярен? Использовать методы из теории фракталов или может еще какой-то вариант? Я этим никогда раньше не занимался, хотел узнать, может кто-то касался этого вопроса?