稳定匹配问题

完美匹配：假设有N个男人和N个女人，如果男人和女人匹配结成一对，是为完美匹配 不稳定匹配： 假设有两对夫妇

那么如何证明这个算法的有效性呢？ 一，证明其为完美匹配： 用反证法，假如最后还余一个单身男性，那么自然以余下的一女子匹配了 二，证明其为最稳定匹配： 用反证法，假如有两个匹配（m1,w1）,(m2,w2)，m1更喜欢w2，w2更喜欢m1。然后由于m1更喜欢w2，所以m1必然向w2求过婚。假如w2拒绝的话，那么原因必然是存在一个她更喜欢的m*的存在。倘若W*存在的话，也论不到资格更低的w2的存在了。