Поиск изоморфных подграфов

Свойства и структура алгоритмов

Общее описание алгоритма

Пусть заданы два графа [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math]. Задача поиска изоморфных подграфов состоит в том, чтобы определить, существует ли у графа [math]\displaystyle{ G }[/math] подграф, изоморфных [math]\displaystyle{ H }[/math], и в случае положительного ответа – предъявить хотя бы один такой подграф.

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

Алгоритм Ульмана решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом

• для фиксированного графа [math]\displaystyle{ H }[/math] время полиномиальное;
• для планарного графа [math]\displaystyle{ G }[/math] время работы линейное (при фиксированном графе [math]\displaystyle{ H }[/math]).