「ダルメジ・メンデルゾーン分解」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
ダルメジとメンデルゾーンによって提案された, 2部グラフの一意的な分解. 略して DM 分解と呼ばれる.最小被覆族の構造に基づいた分解であり, 与えられた2部グラフは, 半順序構造を有する部分グラフの族へと分解される. DM 分解は, 連立1次方程式を解く際にも有用である. 係数行列から得られる2部グラフのDM分解に基づき, 係数行列をブロック三角化することにより, 計算時間を削減することができる. | ダルメジとメンデルゾーンによって提案された, 2部グラフの一意的な分解. 略して DM 分解と呼ばれる.最小被覆族の構造に基づいた分解であり, 与えられた2部グラフは, 半順序構造を有する部分グラフの族へと分解される. DM 分解は, 連立1次方程式を解く際にも有用である. 係数行列から得られる2部グラフのDM分解に基づき, 係数行列をブロック三角化することにより, 計算時間を削減することができる. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|だるめじめんでるぞーんぶんかい]] | ||
2008年11月12日 (水) 15:36時点における最新版
【だるめじめんでるぞーんぶんかい (Dulmage-Mendelsohn decomposition)】
ダルメジとメンデルゾーンによって提案された, 2部グラフの一意的な分解. 略して DM 分解と呼ばれる.最小被覆族の構造に基づいた分解であり, 与えられた2部グラフは, 半順序構造を有する部分グラフの族へと分解される. DM 分解は, 連立1次方程式を解く際にも有用である. 係数行列から得られる2部グラフのDM分解に基づき, 係数行列をブロック三角化することにより, 計算時間を削減することができる.