同形性 (グラフの)

【どうけいせい (graph isomorphism)】

2つのグラフ$G_1=(V_1,A_1)$と$G_2=(V_2,A_2)$に対して, グラフ$G_1$の点と枝の接続関係は保ったまま$V_1$の各点の名前(ラベル)を変えて$V_2$とし, 同時に$A_1$の各枝の名前(ラベル)を変えて$A_2$としてグラフ$G_1$からグラフ$G_2$を得ることが可能であるとき, これらの2つのグラフは同形であるという.