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。
