完全マッチング
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/07 02:21 UTC 版)
「パーマネント (数学)」の記事における「完全マッチング」の解説
任意の正方行列 A := (aij) を、頂点集合 {x1, x2, xn} および {y1, y2, …, yn} を持つ二部グラフで、頂点 xi から頂点 yj へ結んだ辺の重みが aij であるようなものの隣接行列と見ることもできる。xi を yj にマッチさせる 完全マッチング（英語版） σ の重みを、このマッチングに現れる辺すべての重みの総乗と定義するならば weight ( σ ) := ∏ i = 1 n a i , σ ( i ) {\displaystyle \operatorname {weight} (\sigma ):=\prod _{i=1}^{n}a_{i,\sigma (i)}} と書けるから、A のパーマネントはこの二部グラフの完全マッチングすべてに亙る重み付き和に等しいことがわかる。
※この「完全マッチング」の解説は、「パーマネント (数学)」の解説の一部です。
「完全マッチング」を含む「パーマネント (数学)」の記事については、「パーマネント (数学)」の概要を参照ください。
ウィキペディア小見出し辞書の「完全マッチング」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 完全マッチングのページへのリンク
