ダルメジ・メンデルゾーン分解

提供: ORWiki
2007年7月20日 (金) 11:20時点におけるOrsjwiki (トーク | 投稿記録)による版 ("ダルメジ・メンデルゾーン分解" を保護しました。 [edit=sysop:move=sysop])
ナビゲーションに移動 検索に移動

【だるめじめんでるぞーんぶんかい (Dulmage-Mendelsohn decomposition)】

ダルメジとメンデルゾーンによって提案された, 2部グラフの一意的な分解. 略して DM 分解と呼ばれる.最小被覆族の構造に基づいた分解であり, 与えられた2部グラフは, 半順序構造を有する部分グラフの族へと分解される. DM 分解は, 連立1次方程式を解く際にも有用である. 係数行列から得られる2部グラフのDM分解に基づき, 係数行列をブロック三角化することにより, 計算時間を削減することができる.