Задача изоморфизма графов: различия между версиями

Задача определения изоморфизма двух комбинаторных структур исключительно широко распространена и имеет приложения в самых разных областях. В задаче нахождения изоморфизма двух графов искомый изоморфизм представляет собой биекцию (взаимно-однозначное соответствие) множеств вершин графов, порождающую биекцию множеств ребер графов. В случае, если второй граф является копией первого, изоморфизм является отображением графа на самого себя. Такой изоморфизм называется автоморфизмом или, менее формально, симметрией. Множество всех автоморфизмов образует группу относительно операции композиции, называемую группой автоморфизмов. Задача вычисления группы автоморфизмов весьма схожа с задачей определения изоморфизмов.