問題
サイズがN1とN2の二部グラフが与えられる。グラフが以下の条件を満たす時のエッジの最大値を求めよ。
- マッチングの値がc
- 各頂点の次数がd以上
解法
問題の条件を満たす時のエッジの数を方程式で表現し、それの最大値を計算することで答えが求まる。
N1とN2で大きい方の値をa、小さい方の値をbとする。
エッジの数をf(v)で表現する。
まず、bのグラフの中からv個の頂点を選び、aの全ての頂点にエッジを張る。
次に、選ばなかった(b-v)個の頂点から、aの中のc-v個の頂点にエッジを張る。
この時のエッジの数は以下の式で表される。また、この時のマッチングはcとなる。
この式を展開する。
式の形より、下に凸な2次関数であることがわかる。
よって、エッジの最大値はvの最大値もしくは、最小値の時のf(v)となる。
vの最小値は0である。
vの最大値を考える。
問題の条件により、各頂点の字数はd以上でなければならない。よって、(c-v)はd以上となる。
この不等式により、vの最大値はc-dとなる。
f(0)とf(c-d)を計算し、大きい方が答えとなる。
計算量