T-Join
程度★★★ 難度★★
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。
