「マッチング問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【まっちんぐもんだい (matching problem)】 無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング...') |
|||
| 1行目: | 1行目: | ||
| − | 【まっちんぐもんだい (matching problem)】 | + | '''【まっちんぐもんだい (matching problem)】''' |
無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定なマッチングを求める安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般のグラフの場合は問題の構造がより複雑になり多少工夫を要するが, いずれの問題も多項式時間で解くことができる. | 無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定なマッチングを求める安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般のグラフの場合は問題の構造がより複雑になり多少工夫を要するが, いずれの問題も多項式時間で解くことができる. | ||
2007年7月16日 (月) 19:32時点における版
【まっちんぐもんだい (matching problem)】
無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定なマッチングを求める安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般のグラフの場合は問題の構造がより複雑になり多少工夫を要するが, いずれの問題も多項式時間で解くことができる.