同形性 (グラフの)

【どうけいせい (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つのグラフは同形であるという.