Menger數

Menger數亦稱門傑數是圖的一個不變數，Sampathkumar推廣了著名的Menger定理，他提出了Menger圖和Menger數的概念。如果G是一個偶圖，則m(G)= U₀(G)，其中m(G)是G的Menger數，U₀ (G)是G的獨立數。“確定圖的Menger數”問題是NP-困難的。

基本介紹

• 中文名：Menger數
• 外文名：Mengerian number
• 所屬學科：數學（圖論）
• 簡介：圖的一個不變數
• 提出者：Sampathkumar

基本介紹

設x，y為圖G的兩個節點，若G的一個節點子集S，x，y∈S，使得在圖G-S中不再有連x與y的路，則稱S為G的一個(x，y)分離子。

若S是G上的一個(x，y)分離子，但它的任何一個真子集均不是G上的(x，y)分離子，則稱S為極小(x，y)分離子。

含節點最少的(x，y)分離子稱為最小(x，y)分離子。

最小(x，y)分離子中的節點數稱為(x，y)分離數。

兩條以x，y為端點的路，若除x，y以外不再有公共節點，則稱之為獨立的。

連x與y的兩兩獨立的路的最大數稱為(x，y)門傑數，(x，y)門傑數等於(x，y)分離數。

相關介紹

Sampathkumar推廣了著名的Menger定理，他提出了Menger圖和Menger數的概念。

Sampathkumar刻劃了單圈Menger圖，並且提出下面三個未解問題：

問題1　刻劃連通的Menger圖。

問題2　證明n-立方體Q_n的每一個獨立集都是一個Menger集，或者給出反例。

問題3　刻劃滿足的連通圖,其中表示G的獨立數。

關於問題的相關結果如下：

(1) 對任意的n≥ 4，n立方體Q_n不是Menger圖，解決了Sampathkumar提出的未解問題2。

(2) 如果G是一個偶圖，則，其中是G的Menger數，是G的獨立數，部分解決了Sampathkumar提出的未解問題3。

(3) “確定圖的Menger數”問題是NP-困難的。

偶圖的Menger數

定義設G是一個圖，用和分別表示G的頂點集和邊集，頂點x 的鄰集定義為

設S 是圖G的一個獨立集，如果存在使得S的任意兩點都不在G-M的同一個分支中，則稱M分離S。為方便起見，G中分離S 的最小頂點數記為, G中連線S的頂點的內部不相交的路的最大數目記為，顯然

定義 如果獨立集滿足

則稱S是G的一個Menger集。

定義 如果G的每一個獨立集都是Menger集，則稱G是一個Menger圖。

定義 圖G的Menger 數是G中最大Menger集的頂點數，記為。

引理1 如果G是一個森林, 則G是Menger圖。

引理2　設S是G的一個獨立集， 如果對任意的, 我們有

則S是G的Menger集若且唯若S 是G-T的Menger集。

定理對任一偶圖，有。

證　設S是G的最大獨立集使得儘可能大，令

論斷 若Y₀非空，則Y₀的每一個頂點都是H的孤立點。

否則，必存在和使得。由T的定義，的每一個頂點在G中都不與x 相鄰，因此仍然是G的一個最大獨立集，但這與S的定義矛盾。

論斷是空集。

否則，是G中比S 更大的獨立集，與S 的定義矛盾。

注意到T的定義，上面的討論意味著H是一個森林。由引理1，H是Menger圖，於是

S 是的Menger集。由引理2，S也是G的Menger 集。因此，，另一方面，由的定義易知，定理得證。