明蒂定理

明蒂定理(Minty theorem)是反映圖的內在基本組合結構的一個定理。若對於有向圖D的弧以黑、綠、紅三色著色，其中一弧a指定著黑色，其他弧任意著色，則至少以下兩情況之一必發生：或者存在一個包含a弧的由黑、紅兩色弧組成的圈C，且C上的黑色弧方向相同；或者存在一個包含a弧由黑、綠兩色弧組成的上圈B，且B上黑色弧方向相同，這就是明蒂定理。明蒂定理在最大流最小割理論中有用，若對於無向圖的明蒂定理為：對於無向圖G的邊以黑、綠、紅三色任意著色，其中只有一邊指定著黑色，則至少以下兩情況之一必然發生：或者有一個只有黑、紅兩色邊組成的圈；或者有一個只有黑、綠兩色邊組成的上圈，這個定理可推廣到擬陣上。

基本介紹

• 中文名：明蒂定理
• 外文名：Minty theorem
• 別稱：Minty定理
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)

基本介紹

定理1 (明蒂(Minty)定理，1960) 給定一個有向圖，用紅、藍、綠三種顏色給E中的弧染色，已知是紅色弧，則如下論斷有且僅有一個成立：

(1)弧包含在一個圈C中，C是由紅、藍色弧構成的(簡稱紅藍圈)，並且C上所有的紅色弧都屬於C⁺(或都屬於C^-)，這裡的C⁺(C^-)表示給定C的一個定向後，由所有和定向同向(反向)的弧構成的集合；

(2)弧包含在一個反圈v(由中的弧構成的集合)中，v是由紅、綠色弧構成的(簡稱紅綠反圈)，並且所有的紅色弧都屬於v⁺(或都屬於v^-)，這裡的v⁺(v^-)表示給定v的一個定向後，由所有和定向同向(反向)的弧構成的集合。

明蒂定理的證明

證明首先證明(1)和(2)不會同時成立。若不然，設是(1)中的紅藍圈，是(2)中的紅綠反圈。不妨

設，設是路上第一個不屬於X的節點，即，這樣的是存在的，以a表示C上以勘和為端點的弧，因為，故a必定是紅色弧，由(1)知，，這是矛盾的。

下面用反圈法構造性地證明(1)和(2)中一定有一個成立。

開始時令，一般地，設已經有。按照如下原則在中選弧：選中的藍色弧或中的紅色弧，這裡表示中與的定向同向的弧的集合。把被選上的弧的端點放入，得到。重複這個過程，進行到某一階段時必出現下列情況之一：(A)；(B)，而中無邊可選。易見，情形(A)發生時，就得到了使論斷(1)成立的紅藍圈C；情形(B)出現時，就得到了使論斷(2)成立的反圈v，證畢。

相關結論

利用明蒂定理，我們還可以得到下述定理．

定理1 設D是連通有向圖，則如下各結論等價：

(1)D是強連通圖；

(2)D中每一條弧都在某一個有向圈中；

(3)D不含反迴路(即反圈，所有的弧方向一致，從X到)。

定理2 如果一個有向圖是強連通的，那么它的基礎圖一定是2-邊連通圖。

定理3 如果一個有向圖中有一條長度為k的u-v鏈，那么它一定有一條長度不超過k的u-v路。

下面的結論給出了一個有向圖成為強連通圖的充分必要條件。

定理4 有向圖D是強連通圖的充分必要條件是D含有一個封閉的支撐鏈。

一個包含所有有向邊的封閉鏈稱為一個歐拉迴路，而此時有向圖為歐拉有向圖。

定理5 非平凡連通有向圖是歐拉有向圖的充分必要條件是對於每一個節點x，。

下面我們介紹羅賓斯定理(讀者可以直接用歸納法進行證明)。

定理6 (羅賓斯定理，1939) 若且唯若非平凡連通圖是2-邊連通圖時，它有一個強連通定向。