3.5. Задача об изоморфизме графов

Определение. Два взвешенных графа G₁ и G₂ называются изоморфными, если существует взаимооднозначное отображение вершин, сохраняющих расстояние, т.е. после перенумерации вершин графа G₁ получаем ровно граф G₂.

Оценим трудоемкость этой задачи методом прямого перебора.

На выходе имеем два графа из n вершин.

Существует всего n! различных перестановок (перенумераций) для n-элементного массива и при каждой перенумерации необходимо проверить n² – попарных расстояний. Таким образом, трудоемкость этих операций составит T(n) = n!·n².

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

В тоже время для графов некоторых специальных видов (для деревьев) данные алгоритмы существуют.