「マッチング」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【まっちんぐ (matching)】 無向グラフ $G = (V, E)$ の枝部分集合 $M \subseteq A$ で, どの2つの枝も端点を共有しないものをマッチングと...') |
|||
| 1行目: | 1行目: | ||
【まっちんぐ (matching)】 | 【まっちんぐ (matching)】 | ||
| − | + | 無向グラフ $G = (V, E)$ の枝部分集合 $M \subseteq A$ で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 $M \subseteq A$ がマッチングならば,$M$ の枝に接続する点の数は $M$ の要素数の2倍に等しく, またそのときに限って $M$ はマッチングである. $k$ 本の枝からなるマッチングを $k$-マッチングと呼び, 特に $|V|/2$ 本の枝からなるマッチングを完全マッチングと呼ぶ. | |
2007年7月13日 (金) 12:04時点における版
【まっちんぐ (matching)】
無向グラフ $G = (V, E)$ の枝部分集合 $M \subseteq A$ で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 $M \subseteq A$ がマッチングならば,$M$ の枝に接続する点の数は $M$ の要素数の2倍に等しく, またそのときに限って $M$ はマッチングである. $k$ 本の枝からなるマッチングを $k$-マッチングと呼び, 特に $|V|/2$ 本の枝からなるマッチングを完全マッチングと呼ぶ.