来点散装带权拟阵交

https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Quellen/Schrijver-41:MatIntersection.pdf    section 41.3

网上基本没有查到相关的内容，我认真写了（其实是认真翻译）

思路我想大概是这样，首先我们知道了不带权的拟阵交如何求，现在让我们来想出一个能处理带权版本问题的算法，首先我们得想想之前的算法能不能处理带权的拟阵交。

之前的算法输入一个common independent set，输出一个大小比原来大1的common independent set（如果存在），我们如果把它改成：输入一个大小为k的common independent set，并且他是大小为k的所有common independent set当中权值最大的；输出一个大小为k+1的权值最大的common independent set（作者把这样的independent set称为extreme的）

下面我们基本完全照着cardinality版本的拟阵交算法抄过来：我们需要找一个类似增广路的路径 P，然后往exchange graph里面common independent 那一侧放一个假想的点T，把他和增广路在X1中的起点和在X2中的终点连边（T->X1,X2->T），然后我们还得保证找的类似增广路的路径 P 是唯一的，我们构造的这个东西形成一个unique perfect matching，这样我们可以再次用上proposition 5.5，把exchange graph里面common independent 那一侧换成它和P的对称差；别忘了我们还需要保证新的common independent set仍然是extreme的，问题在于应该如何找路径P。

首先我们需要考虑保证形成的那个perfect matching 是unique的，想想我们在拟阵交的算法里是怎么满足这一点的？最短路！我们的路径上有shortcut才会导致存在另外一条包含相同顶点但是访问顺序不同的路径，这会导致我们的匹配不是unique的，因此我们只要保证找的是最短路（边数最少）就行了。

其次我们需要保证新的common independent set仍然是extreme的，也许我们可以给exchange graph的边加上边权。下面我们先不考虑perfect matching 是不是unique了。我们知道matroid intersection并不是一个matroid，比如说最大的common independent set 的大小是k，有一些元素可能不会出现在任何大小为k的common independent set中却具有很大的weight，也就是说maximal weighted common independent set 不一定在cardinality上是maximal的。现在考虑我们找到了一个路径P+假想的点T构成的那个directed circuit，这个circuit正好有偶数个点，其中一半在exchange graph的common independent set S中（包括我们假想的T），另一半不在S中，我们要把在S中的那一部分换成不在S中的那一部分，而且如果新的common independent set权重比之前的更小，这个circuit就不应该存在。因此我们能想到一个听起来很合理的加边权的方法：对于每一个指向e的有向边，如果e是当前common independent set中的点，边的权值就是w(e)；如果e不是当前common independent set中的点，边的权值就是w(e)的相反数（w(T)=0）。我们需要找的就是这样的权值为负的circuit，实际上section 41.3有定理Theorem 41.5. common independent set S 是extreme的 iff. 找不到权值为负的circuit。

最后我们需要考虑到底什么样的路径P可以满足上面的两个条件。首先我们需要Lemma 41.5α.

它的逆否命题正式我们想要的。最后我们实际上找的是：

最后Theorem 41.6.的证明实际上是把整个circuit的权值变成0（通过调整w(T)）并不是像前面说的一样令w(T)=0，不过这些其实没什么影响，整个算法可以这样解释，每次都把假想的T赋一个正的weight，然后通过一些手段获得一个不包含T的、weight却一样的common independent set，由此来找到maximal weighted matroid intersection

最后一部分我没有直观的解释为什么这样没有shortcut，因为我不会，之后想到也许会补上。