マッチング
読み方：まっちんぐ
【英】：matching
【英】：matching
無向グラフ 
の枝部分集合 
で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 がマッチングならば,
の枝に接続する点の数は の要素数の2倍に等しく, またそのときに限って はマッチングである. 
本の枝からなるマッチングを
-マッチングと呼び, 特に 
本の枝からなるマッチングを完全マッチングと呼ぶ.
マッチング (平面上の)
読み方：まっちんぐ
【英】：matching in the plane
【英】：matching in the plane
与えられた平面上の
個の点集合に対して, 2点ずつペアにして
個のペアの集合(完全マッチング)を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチングの重みをに含まれる個のペアの重みの総和として, 重みを最小にする完全マッチング
を見つける問題を平面最小重み完全マッチングという. この問題は
の手間で解けるが, バケット法に基づけば近似的に
の手間で解ける.
「OR事典」の他の用語
| グラフ･ネットワーク： | ベルマン・フォード法 ホールの定理 ポリマトロイド マッチング マッチング問題 マトロイド ユークリッド巡回セールスマン問題 |
| 計算幾何： | バケット法 ボロノイ図 ポリマトロイド マッチング ラゲールボロノイ図 ランダマイゼーション レベル |
- まっちんぐのページへのリンク
