同形性 (グラフの)

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

2つのグラフ$G_{1}=(V_{1},A_{1})\,$と$G_{2}=(V_{2},A_{2})\,$に対して, グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G_1\,} の点と枝の接続関係は保ったまま構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_1\,} の各点の名前(ラベル)を変えて$V_{2}\,$とし, 同時に$A_{1}\,$の各枝の名前(ラベル)を変えて$A_{2}\,$としてグラフ$G_{1}\,$からグラフ$G_{2}\,$を得ることが可能であるとき, これらの2つのグラフは同形であるという.