Изоморфизм

Графы и называются изоморфными, если существует такая биекция множества на множество , что тогда и только тогда, когда . Отображение в этом случае называется изоморфизмом графа на граф .

Тот факт, что графы и изоморфны, записывается так: .

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

Изоморфизм – бинарное отношение на множестве графов. Очевидно, это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у изображения которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.

Характеристики графов, которые сохраняются при изоморфизме, называются инвариантами. Примеры простых инвариантов – число ребер, наличие вершины данной степени, число вершин данной степени, набор степеней (последовательность степеней, упорядоченная по неубыванию), наличие циклов данной длины, число циклов данной длины. Если удается установить, что для двух исследуемых графов некоторый инвариант принимает разные значения, то эти графы неизоморфны. Поиски полной системы легко вычисляемых инвариантов, то есть такой, что совпадение всех этих инвариантов у двух графов гарантировало бы, что эти графы изоморфны, до сих пор не увенчались успехом. Для доказательства того, что два графа изоморфны, необходимо предъявить соответствующую биекцию.