【どうけいせい (graph isomorphism)】
2つのグラフ G 1 = ( V 1 , A 1 ) {\displaystyle G_{1}=(V_{1},A_{1})\,} と G 2 = ( V 2 , A 2 ) {\displaystyle G_{2}=(V_{2},A_{2})\,} に対して, グラフ G 1 {\displaystyle G_{1}\,} の点と枝の接続関係は保ったまま V 1 {\displaystyle V_{1}\,} の各点の名前(ラベル)を変えて V 2 {\displaystyle V_{2}\,} とし, 同時に A 1 {\displaystyle A_{1}\,} の各枝の名前(ラベル)を変えて A 2 {\displaystyle A_{2}\,} としてグラフ G 1 {\displaystyle G_{1}\,} からグラフ G 2 {\displaystyle G_{2}\,} を得ることが可能であるとき, これらの2つのグラフは同形であるという.
