同形性 (グラフの)

出典: ORWiki

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