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

網(wǎng)上基本沒有查到相關(guān)的內(nèi)容，我認真寫了（其實是認真翻譯）

思路我想大概是這樣，首先我們知道了不帶權(quán)的擬陣交如何求，現(xiàn)在讓我們來想出一個能處理帶權(quán)版本問題的算法，首先我們得想想之前的算法能不能處理帶權(quán)的擬陣交。

之前的算法輸入一個common independent set，輸出一個大小比原來大1的common independent set（如果存在），我們?nèi)绻阉某桑狠斎胍粋€大小為k的common independent set，并且他是大小為k的所有common independent set當中權(quán)值最大的；輸出一個大小為k+1的權(quán)值最大的common independent set（作者把這樣的independent set稱為extreme的）

下面我們基本完全照著cardinality版本的擬陣交算法抄過來：我們需要找一個類似增廣路的路徑 P，然后往exchange graph里面common independent 那一側(cè)放一個假想的點T，把他和增廣路在X1中的起點和在X2中的終點連邊（T->X1,X2->T），然后我們還得保證找的類似增廣路的路徑 P 是唯一的，我們構(gòu)造的這個東西形成一個unique perfect matching，這樣我們可以再次用上proposition 5.5，把exchange graph里面common?independent 那一側(cè)換成它和P的對稱差；別忘了我們還需要保證新的common independent set仍然是extreme的，問題在于應(yīng)該如何找路徑P。

首先我們需要考慮保證形成的那個perfect matching 是unique的，想想我們在擬陣交的算法里是怎么滿足這一點的？最短路！我們的路徑上有shortcut才會導(dǎo)致存在另外一條包含相同頂點但是訪問順序不同的路徑，這會導(dǎo)致我們的匹配不是unique的，因此我們只要保證找的是最短路（邊數(shù)最少）就行了。

其次我們需要保證新的common independent set仍然是extreme的，也許我們可以給exchange graph的邊加上邊權(quán)。下面我們先不考慮perfect matching 是不是unique了。我們知道m(xù)atroid intersection并不是一個matroid，比如說最大的common independent set 的大小是k，有一些元素可能不會出現(xiàn)在任何大小為k的common independent set中卻具有很大的weight，也就是說maximal weighted common independent set 不一定在cardinality上是maximal的?，F(xiàn)在考慮我們找到了一個路徑P+假想的點T構(gòu)成的那個directed circuit，這個circuit正好有偶數(shù)個點，其中一半在exchange graph的common independent set S中（包括我們假想的T），另一半不在S中，我們要把在S中的那一部分換成不在S中的那一部分，而且如果新的common independent set權(quán)重比之前的更小，這個circuit就不應(yīng)該存在。因此我們能想到一個聽起來很合理的加邊權(quán)的方法：對于每一個指向e的有向邊，如果e是當前common independent set中的點，邊的權(quán)值就是w(e)；如果e不是當前common independent set中的點，邊的權(quán)值就是w(e)的相反數(shù)（w(T)=0）。我們需要找的就是這樣的權(quán)值為負的circuit，實際上section 41.3有定理Theorem 41.5. common independent set S 是extreme的 iff. 找不到權(quán)值為負的circuit。

最后我們需要考慮到底什么樣的路徑P可以滿足上面的兩個條件。首先我們需要Lemma 41.5α.

它的逆否命題正式我們想要的。最后我們實際上找的是：

最后Theorem 41.6.的證明實際上是把整個circuit的權(quán)值變成0（通過調(diào)整w(T)）并不是像前面說的一樣令w(T)=0，不過這些其實沒什么影響，整個算法可以這樣解釋，每次都把假想的T賦一個正的weight，然后通過一些手段獲得一個不包含T的、weight卻一樣的common independent set，由此來找到maximal weighted matroid intersection

最后一部分我沒有直觀的解釋為什么這樣沒有shortcut，因為我不會，之后想到也許會補上。