三維匹配

喺數學嘅圖論入面，**三維匹配**（英文：3-dimensional matching）係二分圖匹配（又叫做二維匹配）推廣到三部分超圖嘅版本。呢啲超圖嘅超邊都係包含3個頂點（而唔係普通圖嘅邊噉，包含2個頂點）。

三維匹配，成日簡寫做**3DM**，同時都係一條好出名嘅計算問題嘅名：喺一幅指定嘅超圖入面，搵一個最大嘅三維匹配。3DM 係第一批被證明係NP困難嘅問題之一。

## 定義
設 *X*、*Y* 同 *Z* 係有限集，而 *T* 係 *X*&nbsp;×&nbsp;*Y*&nbsp;×&nbsp;*Z* 嘅子集。即係話，*T* 由三元組 (*x*,&nbsp;*y*,&nbsp;*z*) 組成，其中 *x*&nbsp;∈&nbsp;*X*，*y*&nbsp;∈&nbsp;*Y*，同 *z*&nbsp;∈&nbsp;*Z*。噉 *M*&nbsp;⊆&nbsp;*T* 係一個三維匹配，如果以下條件成立：對於任何兩個唔同嘅三元組 (*x*1,&nbsp;*y*1,&nbsp;*z*1)&nbsp;∈&nbsp;*M* 同 (*x*2,&nbsp;*y*2,&nbsp;*z*2)&nbsp;∈&nbsp;*M*，我哋有 *x*1&nbsp;≠&nbsp;*x*2、*y*1&nbsp;≠&nbsp;*y*2，同埋 *z*1&nbsp;≠&nbsp;*z*2。

### 例子
右邊幅圖展示咗三維匹配。集合 *X* 用紅色點標記，*Y* 用藍色點標記，而 *Z* 用綠色點標記。圖 (a) 顯示咗集合 *T*（灰色區域）。圖 (b) 顯示咗一個三維匹配 *M*，其中 |*M*|&nbsp;=&nbsp;2，而圖 (c) 顯示咗一個三維匹配 *M*，其中 |*M*|&nbsp;=&nbsp;3。

圖 (c) 中展示嘅匹配 *M* 係一個「最大三維匹配」，即係話，佢最大化咗 |*M*|。圖 (b)–(c) 中展示嘅匹配係「極大三維匹配」，即係話，佢哋唔可以通過添加更多嚟自 *T* 嘅元素嚟擴展。

### 同二分圖匹配嘅比較
一個「二維匹配」可以用一個完全類似嘅方式嚟定義。設 *X* 同 *Y* 係有限集，而 *T* 係 *X*&nbsp;×&nbsp;*Y* 嘅子集。噉 *M*&nbsp;⊆&nbsp;*T* 係一個二維匹配，如果以下條件成立：對於任何兩個唔同嘅pair (*x*1,&nbsp;*y*1)&nbsp;∈&nbsp;*M* 同 (*x*2,&nbsp;*y*2)&nbsp;∈&nbsp;*M*，我哋有 *x*1&nbsp;≠&nbsp;*x*2 同 *y*1&nbsp;≠&nbsp;*y*2。

喺二維匹配嘅情況下，集合 *T* 可以解釋做二分圖 *G*&nbsp;=&nbsp;(*X*,&nbsp;*Y*,&nbsp;*T*) 入面嘅邊嘅集合；*T* 入面嘅每條邊都連接 *X* 入面嘅一個頂點到 *Y* 入面嘅一個頂點。噉一個二維匹配就係圖 *G* 入面嘅一個 匹配，即係一組pairwise唔相鄰嘅邊。

因此，三維匹配可以解釋做匹配推廣到超圖：集合 *X*、*Y* 同 *Z* 包含頂點，*T* 嘅每個元素都係一條超邊，而集合 *M* 由pairwise唔相鄰嘅邊組成（唔具有公共頂點嘅邊）。喺二維匹配嘅情況下，我哋有 Y&nbsp;=&nbsp;Z。

### 同集合打包嘅比較
一個三維匹配係一個 集合打包 嘅特殊情況：我哋可以將 *T* 嘅每個元素 (*x*,&nbsp;*y*,&nbsp;*z*) 解釋做 *X*&nbsp;∪&nbsp;*Y*&nbsp;∪&nbsp;*Z* 嘅一個子集 {*x*,&nbsp;*y*,&nbsp;*z*}；噉一個三維匹配 *M* 由pairwise disjoint嘅子集組成。

## 判定問題
喺計算複雜性理論入面，「三維匹配」係以下判定問題嘅名：畀定一個集合 *T* 同一個整數 *k*，決定係咪存在一個三維匹配 *M*&nbsp;⊆&nbsp;*T*，其中 |*M*|&nbsp;≥&nbsp;*k*。

已知呢個判定問題係NP完全嘅；係Karp嘅21個NP完全問題之一。 即使喺特殊情況下，當 *k*&nbsp;=&nbsp;|*X*|&nbsp;=&nbsp;|*Y*|&nbsp;=&nbsp;|*Z*|，而且每個元素最多包含喺 3 個集合入面嗰陣，佢都係 NP完全嘅，即係話，當我哋想要喺一個 3-regular 超圖入面搵一個完美匹配嘅時候。 喺呢種情況下，一個三維匹配唔單止係一個集合打包，仲係一個 精確覆蓋：集合 *M* 精確噉覆蓋 *X*、*Y* 同 *Z* 嘅每個元素一次。 證明係通過由 3SAT 嘅歸約。畀定一個 3SAT 嘅instance，我哋構造一個 3DM 嘅instance 如下：

* 對於每個變數 *x<sub>i</sub>*，有一個形狀似輪嘅「變數gadget」。佢由重疊嘅三元組組成。三元組嘅數量係 *x<sub>i</sub>* 喺公式入面出現次數嘅兩倍。有兩種方法可以覆蓋gadget入面所有嘅頂點：一種係揀所有偶數索引嘅三元組，另一種係揀所有奇數索引嘅三元組。呢兩種方法分別對應於將 *x<sub>i</sub>* 設置為「真」或者「假」。 「真」選擇會喺每個奇數索引嘅三元組入面留低啱啱好一個未覆蓋嘅頂點，而「假」選擇會喺每個偶數索引嘅三元組入面留低啱啱好一個未覆蓋嘅頂點。
* 對於每個clause *x<sub>i</sub>* u *x<sub>j</sub>* u *x<sub>k</sub>*，有一個形狀似玫瑰嘅「clause gadget」。佢由三個重疊嘅三元組組成，每個三元組對應clause入面嘅一個變數。佢可以被覆蓋，當且僅當至少一個節點冇被變數gadget嘅選擇覆蓋。
* 由於有可能兩個或者更多嘅節點冇被覆蓋，我哋都需要一個「垃圾收集gadget」。佢嘅形狀似一個更大嘅玫瑰。佢由幾個重疊嘅三元組組成，每個三元組對應喺變數gadget入面可以冇被覆蓋嘅一個頂點。呢啲gadget嘅數量係噉樣決定嘅，佢哋可以被精確噉覆蓋，當且僅當存在一個滿足嘅賦值。

### 特殊情況
存在啲多項式時間演算法，用嚟解決dense超圖入面嘅3DM問題。

## 最佳化問題
一個「最大三維匹配」係一個最大嘅三維匹配。喺計算複雜性理論入面，呢個同時都係以下 最佳化問題 嘅名：畀定一個集合 *T*，搵一個三維匹配 *M*&nbsp;⊆&nbsp;*T*，佢可以最大化 *|M|*。

由於上面描述嘅判定問題係 NP完全嘅，所以呢個最佳化問題係 NP困難 嘅，因此好似冇多項式時間演算法可以搵到一個最大三維匹配。但係，有啲有效率嘅多項式時間演算法可以搵到一個最大 二分圖匹配（最大二維匹配），例如 Hopcroft–Karp 演算法。

### 近似演算法
有一個好簡單嘅多項式時間 3-近似演算法，用嚟解決三維匹配：搵任何極大三維匹配。 就好似一個極大匹配喺一個最大匹配嘅因子 2 範圍內一樣， 一個極大三維匹配喺一個最大三維匹配嘅因子 3 範圍內。

對於任何常數 ε&nbsp;>&nbsp;0，都有一個多項式時間 (4/3&nbsp;+&nbsp;ε)-近似演算法，用嚟解決三維匹配。

但係，要達到更好嘅近似因子可能好難：呢個問題係 APX完全 嘅，即係話，佢好難喺某個常數範圍內 近似。

要達到最大三維匹配嘅 95/94 近似因子，同埋最大四維匹配嘅 48/47 近似因子係 NP困難嘅。即使喺限制到每個元素啱啱好出現兩次嘅instance入面，呢個難度仍然存在。

### 並行演算法
喺 大規模並行通訊 模型入面，有各種用於三維匹配嘅演算法。

## 睇埋

* NP完全問題列表
* 彩虹獨立集 – 一個可以由三維匹配歸約嘅問題。
* 數值三維匹配

## 注釋

## 參考文獻

* .
* .
* .
* .
* .
* .
* .

## 出面嘅連結

* 一個用 JavaScript 實現嘅互動可視化