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

Пусть даны два графа <math>G_1 = (V_1, E_1) \; </math> и <math>G_2 = (V_2, E_2) \;</math>. Изоморфизм графа <math>G_1 \;</math> на <math>G_2 \;</math> представляет собой биекцию <math>V_1 \;</math> на <math>V_2 \;</math>, такую, что она порождает биекцию <math>E_1 \;</math> на <math>E_2 \;</math>. Если <math>G_1 = G_2 \; </math>, то изоморфизм является автоморфизмом <math>G_1 \;</math>. Множество всех автоморфизмов <math>G_1 \;</math> образует группу относительно операции композиции, называемую группой автоморфизмов <math>G_1 \; </math> и обозначаемую <math>Aut(G_1) \;</math>.

На рис. 1 представлены два изоморфных графа, а также изоморфизм между ними и группа автоморфизмов первого графа.