基本介紹
基本介紹,其他形式的Menger定理,
基本介紹
1927年，Menger證明了圖的連通性與圖中連線兩個頂點的不相交路的數目有關。Menger定理非常有用，由它產生了許多關於圖的連通性的很多變種結論，而且它與Hall匹配定理與最大流量最小割定理以及其他一些離散數學中的重要結論都密切相關。
下面的定理就是Menger定理原先提出來的原始形式。
定理1(頂點形式的Menger定理) 設x和y為圖G中兩個不相鄰的頂點，則G中內部不相交的(x，y)-路的最大數目=G中最小的xy-頂點分隔集的頂點數。
證明 將下文定理7用於G的對稱有向圖上即得。
推論2(Menger定理) 設p(G)≥k+1，則G為k-連通的若且唯若G中任意兩個不相同頂點至少被k條內部不交的路所連線。
證明 必要性。反證，假設k-連通圖G中存在兩個頂點u，v，使得G中內部不相交的(u，v)-路的最大數日為m<k。若u，v不相鄰，則由定理1知，G中最小的uv-頂點分隔集的頂點數為m，從而κ(G)≤m<k，這與G為k-連通相矛盾。若u，v相鄰，則從G中去掉所有連線u，v的邊後，所得的圖中有小於或等於m-1條內部不交的(u，v)-路，從而由定理1知，該圖中存在uv-頂點分隔集U，使得|U|≤m-1(≤k-2≤p(G)-3)。於是G-U-{u}或G-U-{v}不連通。這導致κ(G)≤m≤k，矛盾。
充分性。反證，假設非平凡圖G不是k-連通的，即κ(G)<k，但是G中任意兩個不同頂點至少被k條內部不相交的路所連線。首先G不會是完全圖。於是，G中存在頂點集W，|W|=κ(G)，使得G-W不連通。任取G-W的兩個分支，並在其中各取一頂點u和v。顯然，u和v不相鄰，而W為G中的uv-頂點分隔集。但是由定理假設知，G中有k條內部不交的u-v路，因此由定理1知，G中最小的uv-頂點分隔集的頂點數大於或等於k>κ(G)，矛盾。證畢。
其他形式的Menger定理
引理3 設網路N的源為x，匯為y，且每弧的容量都為1，則
1)N中最大流的值等於N中弧不重的有向(x,y)-路的最大數目。
2)N中最小割的容量等於N中最小的xy-弧分隔集的弧數。
定理4(弧形式的Menger定理) 設x和y為有向圖D中任意兩頂點，則D中弧不重的有向(x,y)-路的最大數目=D中最小的xy-弧分隔集的弧數。
與後面無向圖“頂點形式”的定理7和定理9相似，我們有以下無向圖“邊形式”的兩個定理。令人驚奇的是，直到1955年，它們才首先被Ford和Fulkerson證明出來。
定理5(邊形式的Menger定理) 設x和y為圖G中任意兩頂點，則G中邊不重的(x，y)-路的最大數目=G中最小xy-邊分隔集的邊數。
證明 作圖G的對稱有向圖，再用定理4即得。
G為k-邊連通的↔從G中去掉任何k-1條邊都不能使G不連通↔對G中任意兩個頂點x和y，G中最小的xy-邊分隔集的邊數至少為k，由此，以下推論是顯然的。
推論6(Menger定理) G為k-邊連通的若且唯若G中任意兩個頂點都至少被k條邊不重的路所連線。
定理7(頂點形式的Menger定理) 設x和y為有向圖D中兩個不同頂點，且D中沒有連x到y的弧，則D中內部不相交的有向(x，y)-路的最大數目=D中最小的xy-頂點分隔集的頂點數。
證明 由D作有向圖D’如下：
1)將每個v∈V\{x，y}分成二新頂點v'及v''，並連以新弧(v'，v')。
2)將D中以v∈V\{x，y}為起點的弧代之以v'為起點的弧；以v為終點的弧代之以v''為終點的弧。
於是易見，D'中一有向(x，y)-路與D中一有向(x，y)-路之間存在一一對應關係(通過將D'中一有向(x，y)-路上每一(v'，v'')弧縮成v；或將D中一有向(x，y)-路的每一中間頂點v分裂成弧(v'，v''))。又由於易見D'中二有向(x，y)-路為弧不重的↔D中對應的二有向(x，y)-路為內部不相交的。因此，D'中弧不重的有向(x，y)-路的最大數目=D中內部不相交的有向(x，y)-路的最大數目。
類似地，D'中最小的xy-弧分隔集的弧數=D中最小的xy-頂點分隔集的頂點數。再用定理4問題得證。證畢。
