Изоморфные графы
Что такое изоморфизм? Изоморфизм устанавливает отношение равенства между графами G и Н (G=H – графы изоморфны). Два графа изоморфны, если между множествами их вершин можно установить взаимно-однозначное соответствие, сохраняющее смежность. Маленькая проверка: мысленно «деформируйте» один из графов так, чтобы он стал похож на второй. Если получилось, то эти графы изоморфны. Другими словами, два графа равны, если их соответствующие вершины соединены одинаково. Например, поиграем в спички: соберём звезду и пятиугольник. Итак, перед нами две фигуры. Но точно ли они различаются? Заметим, что в 1-м графе можно переместить вниз спички, соединяющие вершины (5, 3), (4, 2) и (5, 2). В результате, получится такой же 5-угольник, что и на 2-м рисунке.