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

Граф представляет собой пару G = (V, E) конечных множеств, где E – множество пар (v, w) элементов V. Элементы множества V называются вершинами (или узлами), элементы множества E – ориентированными ребрами (или дугами). Контрарная пара (v, w); (w, v) ориентированных ребер (<math>v \ne w \; </math>) называется неориентированным ребром и обозначается {v, w}. Ориентированное ребро вида (v, v) также считается неориентированным и называется циклом (или петлей). Далее под «ребрами» будут пониматься неориентированные ребра, ориентированные ребра или оба типа ребер.

Пусть даны два графа <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>.