「同形性 (グラフの)」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(他の1人の利用者による、間の1版が非表示)
2行目: 2行目:
  
 
2つのグラフ<math>G_1=(V_1,A_1)\,</math>と<math>G_2=(V_2,A_2)\,</math>に対して, グラフ<math>G_1\,</math>の点と枝の接続関係は保ったまま<math>V_1\,</math>の各点の名前(ラベル)を変えて<math>V_2\,</math>とし, 同時に<math>A_1\,</math>の各枝の名前(ラベル)を変えて<math>A_2\,</math>としてグラフ<math>G_1\,</math>からグラフ<math>G_2\,</math>を得ることが可能であるとき, これらの2つのグラフは同形であるという.
 
2つのグラフ<math>G_1=(V_1,A_1)\,</math>と<math>G_2=(V_2,A_2)\,</math>に対して, グラフ<math>G_1\,</math>の点と枝の接続関係は保ったまま<math>V_1\,</math>の各点の名前(ラベル)を変えて<math>V_2\,</math>とし, 同時に<math>A_1\,</math>の各枝の名前(ラベル)を変えて<math>A_2\,</math>としてグラフ<math>G_1\,</math>からグラフ<math>G_2\,</math>を得ることが可能であるとき, これらの2つのグラフは同形であるという.
 +
 +
[[Category:グラフ・ネットワーク|どうけいせい]]

2008年11月13日 (木) 12:48時点における最新版

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

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