Question

T-Join

在一张图上选出偶数个点（通常标作 T 集合，也就是 T-Join 的 T；因为是代表集合，所以 T 要大写），然后再选出许多条边，让选中的点都是连著奇数条选中的边，让没选中的点都是连著偶数条选中的边，这些边就叫做一个 T-Join。

这个定义是参考 Euler Trail 设计出来的。各位如果熟悉 Euler Trail 的起点和终点是“奇点”，中继点是“偶点”，那麽就能了解这个定义的前因后果了！在图上选出的偶数个点，正是 Euler Trail 的起点和终点。额外添上几个环，便是 T-Join 了。

Minimum Weight T-Join

一张无向图上，边的权重总和最小的 T-Join，可能有许多种。

Minimum Weight T-Join 可以看作是 Matching 的“匹配边”改成了“匹配路径”。Minimum Weight T-Join 是“最短路径”与“匹配”两者的结合，同时具有两者的特性。

一、最短路径性质：一个 Minimum Weight T-Join 的每一条路径，都是最短路径。一个 Minimum Weight T-Join 随便拿掉几条边，仍然是 Minimum Weight T'-Join。

这个道理，就是“最短路径截下一段还是最短路径”的道理。

二、匹配性质：可以用一道数学式子表达。

  Minimum Weight (A⊕B)-Join
= Minimum Weight A-Join ⊕ Minimum Weight B-Join。

⊕是对称差集，也就是 XOR。此数学式即是 XOR 的分配律。

证明就留给大家。可以使用最短路径性质证明。

正权重图的 Minimum Weight T-Join 演算法

一、替 T 求出所有两点之间的最短路径长度。
二、替 T 找一个最小权匹配。此即 Minimum Weight T-Join。

最小权匹配配合最短路径，如此求得的匹配路径们，是不会有边重叠的。两条匹配路径，一旦有边重叠，只要去掉重叠的边，仍然形成两条匹配路径，而且势必形成权重更小的 T-Join。

根据最短路径特性，求得的匹配路径都是最短路径；根据最小权匹配特性，求得的匹配路径们的权重总和会最小。由此两点，求得的是 Minimum Weight T-Join。

负权重图的 Minimum Weight T-Join 演算法

只适用于没有负环的情况。有负环成为 NP-complete 问题。

手法是将负权重图改为正权重图，并利用正权重图的 Minimum Weight T-Join 来倒推出负权重图的 Minimum Weight T-Join。

一、图上所有负边构成 N-Join。
二、把图上所有负边变号，整张图变成只有非负边。
三、求出新图的 Minimum Weight (T⊕N)-Join。
四、与 N-Join 进行 XOR，即得到原图的 Minimum Weight T-Join。
　　权重相差“所有负边权重总和的绝对值”。

转换的过程中，用到两个概念：甲、在同一张图上，从 Minimum Weight T-Join 上面拿掉几条边，仍然是一个 Minimum Weight T-Join。乙、把一张图上的边，而且是一个 Minimum Weight T-Join 上的边，权重由正变负之后，这个 Minimum Weight T-Join 的位置仍然不变。

证明过程可以写成简单的数学式子：

w(T) = w(T-N) + w(T∩N)

     = w(T-N) - w(N-T) + w(N-T) + w(T∩N)
       ^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^
     = |w|(T⊕N) + w(N)
       ^^^^^^^^^   ^^^^

w(T)：原图的 Minimum Weight T-Join 的权重。
|w|(T)：原图所有权重取绝对值变成新图，新图的 Minimum Weight T-Join 的权重。
N：原图所有负边会构成 Minimum Weight N-Join。

应用

无向图的两点间最短路径：以起点与终点作为 T。
无向图的中国邮差问题：以所有奇点作为 T。

b-Matching

b-Matching

b-factor = perfect b-matching
每个点刚好连著 b 条边的子图

perfect (b,u)-matching = u-capacitated perfect b-matching
每个点刚好连著 b 条边，每条边可重複使用，最多使用 u 次。

(b,u)-matching = u-capacitated b-matching
每个点最多连著 b 条边，每条边可重複使用，最多使用 u 次。

b-matching
每个点最多连著 b 条边

1-matching = matching
一般图匹配

这些问题可以从第一个 reduce 到最后一个，
就算是 weighted 的版本也是 P 问题，不过演算法很难很难的。
再来，就算每个节点各自设定不同的 b 值，也是 P 问题。

演算法

因为 P 的演算法太难了，所以这裡提供假 P 的演算法。

针对每一个节点，自己拷贝变成 b 份，此节点的邻点也都拷贝一份。
若原本有节点 i 与邻点 j 有边，则拷贝的 i 与拷贝的 j 之间也有边，形成 Kb(i),degree(i)。
然后拷贝出的邻点，有相对应的就连一条边。
然后求最大匹配即可。

Stable Matching

但愿人长久，千里共婵娟。《苏轼．水调歌头》

稳定婚姻问题（Stable Marriage Problem）

一家婚友社将 N 位男士与 N 位女士进行媒合，一位男士配一位女士，共要撮合 N 对婚姻。

每位男士各自拥有一个好感度列表，对 N 位女性各以 1 到 N 的数字进行排名。每位女士各自亦有一个好感度列表，对 N 位男性各以 1 到 N 的数字进行排名。

媒合时必须避免，不是伴侣的某男某女，出现婚外情的倾向：“男对女说：我爱你比爱我妻子还深。同时女对男说：我爱你比爱我丈夫还深。”请找出适合的配对方式。

演算法（Gale-Shapley Algorithm）

这个问题已被证明恰有两解（或一解，当此两解相同时），其中一解称为男士最佳解，另一解则称为女士最佳解。男士最佳解的演算法如下：

1. N 位男士各自向自己最喜爱的女士求婚。
2. N 位女士各自从自己的求婚者中，挑最喜爱的那位男士订婚，但是往后可背约。
   没有求婚者的女士，就只好等等。
3. 失败的男士们，只好各自向自己次喜爱的女士求婚。
4. N 位女士各自从自己的求婚者中，挑最喜欢的那位男士订婚，但是往后可背约。
   已订婚却有更喜爱的男士求婚的女士，就毁约，改为与此男士订婚。
　 没有求婚者的女士，就只好再等等。
5. 重複 3. 4.直到形成 N 对伴侣为止。

男士不断降格以求，女士不断水涨船高，最后达成平衡。

女士最佳解的演算法则改为由女士主动求婚即可。

时间複杂度是 O(N^2)。

UVa 11119 1175 ICPC 3837

Popular Matching

Popular matching, SIAM J. Computing, Vol. 37, No. 4, pp. 1030-1045.

ICPC 6304