LINUX.ORG.RU

Задача о подграф изоморфизме


0

0

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

Задача о подграф изоморфизме: дано два графа, второй предположительно является подграфом первого, проверить это утверждение, и найти вершины в первом графе, которые соответствуют второму.


Если влоб, то просто перебор всех перестановок индексов вершин матрицы связности крупного графа, приводящих к проявлению на ней матрицы связности более мелкого. Но это жуткий оверхэд.

mclaudt
()
Ответ на: комментарий от mclaudt

Уже нашел статью Ульмана, там как раз этот алгоритм применяется + эвристики для обрезания некоторых заранее плохих путей поиска. А вобще это задача NP полная, так что точное решение всеравно будет экспоненциальное.

recon88
() автор топика
Ответ на: комментарий от recon88

На практике все равно попадаются, условия, сужающие перебор, некоторые - значительно, значит точное решение можно будет получить и не за экспоненту.

x4DA ★★★★★
()
Ответ на: комментарий от ftor

человек наверное имел ввиду различные частные случаи, когда имея некоторые допущение действительно можно решить за полиномиальное время(а такие случаи есть). Например решение «пятнашек» - NP задача, хотя введением эвристик можно получить очень быстрое время решения(за счет направленого перебора), а все потому что условие задачи удовлетворяет некоторым условиям

recon88
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.