「マッチング」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
【まっちんぐ (matching)】
+
'''【まっちんぐ (matching)】'''
  
 
無向グラフ <math>G = (V, E)\,</math> の枝部分集合 <math>M \subseteq A\,</math> で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ.  枝部分集合 <math>M \subseteq A\,</math> がマッチングならば,<math>M\,</math> の枝に接続する点の数は <math>M\,</math> の要素数の2倍に等しく, またそのときに限って <math>M\,</math> はマッチングである. <math>k\,</math> 本の枝からなるマッチングを
 
無向グラフ <math>G = (V, E)\,</math> の枝部分集合 <math>M \subseteq A\,</math> で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ.  枝部分集合 <math>M \subseteq A\,</math> がマッチングならば,<math>M\,</math> の枝に接続する点の数は <math>M\,</math> の要素数の2倍に等しく, またそのときに限って <math>M\,</math> はマッチングである. <math>k\,</math> 本の枝からなるマッチングを
 
<math>k\,</math>-マッチングと呼び, 特に <math>|V|/2\,</math> 本の枝からなるマッチングを完全マッチングと呼ぶ.
 
<math>k\,</math>-マッチングと呼び, 特に <math>|V|/2\,</math> 本の枝からなるマッチングを完全マッチングと呼ぶ.
 +
 +
[[Category:グラフ・ネットワーク|まっちんぐ]]
 +
 +
[[Category:計算幾何|まっちんぐ]]

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

【まっちんぐ (matching)】

無向グラフ の枝部分集合 で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 がマッチングならば, の枝に接続する点の数は の要素数の2倍に等しく, またそのときに限って はマッチングである. 本の枝からなるマッチングを -マッチングと呼び, 特に 本の枝からなるマッチングを完全マッチングと呼ぶ.