研究

fractional matchingってなんですか?

論文を読んでいたら出てきて、ちょっと調べた感じ日本語の情報がなかったので。

マッチングとは

グラフが与えられたとき、頂点を共有しない辺の集合をマッチングと呼びます。

これはグラフ G(V, E) に対して、E -> {0,1} である関数 f と捉えることもできます。ただし各頂点に対して の和は1以下でなければなりません(つまり0か1です)。

fractional matchingとは

マッチングでは関数の値域(終域)が {0, 1} でしたが、それが [0, 1] であるような関数をfractional matchingと言います。0か1だったのが0から1に連続的に拡張したマッチングということですね。ここでも各頂点での和は1以下でなければなりません。

参考