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

Постановка задачи

Пусть заданы два графа [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]).

Алгоритм VF2 разработан специально для применения на больших графах.