T-Join

T-Join

在一張圖上選出偶數個點(通常標作T集合,也就是T-Join的T;因為是代表集合,所以T要大寫),然後再選出許多條邊,讓選中的點都是連著奇數條選中的邊,讓沒選中的點都是連著偶數條選中的邊,這些邊就叫做一個T-Join。

這個定義是參考Euler Path設計出來的。各位如果熟悉Euler Path的起點和終點是「奇點」,中繼點是「偶點」,那麼就能了解這個定義的前因後果了!在圖上選出的偶數個點,正是Euler Path的起點和終點。額外添上幾個環,便是T-Join了。

Minimum Weight T-Join

一張無向圖上,邊的權重總和最小的T-Join,可能有許多種。

Minimum Weight T-Join可以看作是Matching的「匹配邊」改成了「匹配路徑」。匹配路徑數量是T的一半。每一條匹配路徑,顯然必須是最短邊互斥路徑。

Minimum Weight T-Join是「最短邊互斥路徑」與「最小權匹配」兩者結合,同時具有兩者性質。

一、最短邊互斥路徑性質:一個Minimum Weight T-Join由許多條匹配路徑組成,數量是T的一半。每一條匹配路徑,都是最短邊互斥路徑。

二、最小權匹配性質:兩種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演算法【尚待確認】

只適用於沒有負環的情況。有負環成為NP-complete問題。

負權重圖改為正權重圖,然後利用正權重圖的Minimum Weight T-Join反向推導負權重圖的Minimum Weight T-Join。

一、圖上所有負邊,恰好構成Minimum N-Join。
  N是所有負邊的所有端點,而且重複次數是奇數。
  N是連著奇數條負邊的點。
二、原圖所有負邊變號,得到新圖。
  求出新圖的Minimum Weight (T⊕N)-Join。
三、新圖的Minimum Weight (T⊕N)-Join,
  原圖的Minimum N-Join,
  兩者的互斥聯集,即是原圖的Minimum Weight T-Join。

我目前讀過的文獻,正確性證明千篇一律存在漏洞。

證明方式:原圖的Minimum 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̅-T̅) + w(N̅-T̅) + w(T̅∩N̅)
       ^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^
     = |w|(T̅⊕N̅) + w(N̅)
       ^^^^^^^^   ^^^^
     = |w|(T⊕N) + w(N̅)

T:取偶數個點。
T̅:Minimum Weight T-Join的所有邊。
N:所有負邊的所有端點,而且重複次數是奇數。
N̅:所有負邊。顯然構成了Minimum Weight N-Join。
T⊕N:T和N的互斥聯集。
T⊕N:Minimum Weight (T⊕N)-Join的所有邊。
w():每條邊的權重總和。
|w|():每條邊的權重,先取絕對值(所有負邊變號)再總和。
w(T̅):Minimum Weight T-Join的權重。
w(N̅):Minimum Weight N-Join的權重。所有負邊的權重總和。

當|w|(T⊕N)達到最小值,而w(N̅)是常數,則w(T̅)也達到最小值。

大家只證明到這一步。大家並未證明原圖的Minimum Weight (T⊕N)-Join和新圖的Minimum Weight (T⊕N)-Join如何對應。

我認為兩者根本無法對應。一般來說,圖上某些邊,權重增減、甚至變號,Minimum Weight T-Join都會大幅改變。

我認為上述演算法是古人瞎掰的。負權重圖的多項式時間演算法,也許根本不存在。

備忘

一、正權重圖,最短路徑截取一段,仍是最短路徑。Minimum Weight T-Join拿掉一些邊(T隨之變成T'),仍是Minimum Weight T'-Join。

二、Minimum Weight T-Join內部取一些正邊轉負邊【這部分是錯的】、外部取一些負邊轉正邊。原圖也轉換這些邊,成為新圖。它仍是新圖的Minimum Weight T-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²)。

UVa 11119 1175 ICPC 3837

Popular Matching

《Algorithmics of Matching Under Preferences》

ICPC 6304