Menger數亦稱門傑數是圖的一個不變數，Sampathkumar推廣了著名的Menger定理，他提出了Menger圖和Menger數的概念。如果G是一個偶圖，則m(G)= U0(G)，其中m(G)是G的Menger數，U0 (G)是G的獨立數。“確定圖的Menger數”問題是NP-困難的。
基本介紹
- 中文名：Menger數
- 外文名：Mengerian number
- 所屬學科：數學（圖論）
- 簡介：圖的一個不變數
- 提出者：Sampathkumar
基本介紹,相關介紹,偶圖的Menger數,
基本介紹
設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-立方體Qn的每一個獨立集都是一個Menger集，或者給出反例。
問題3 刻劃滿足
的連通圖,其中
表示G的獨立數。
關於問題的相關結果如下：
(1) 對任意的n≥ 4，n立方體Qn不是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的頂點的內部不相交的路的最大數目記為
，顯然
定義 如果獨立集
滿足
定義 如果G的每一個獨立集都是Menger集，則稱G是一個Menger圖。
定義 圖G的Menger 數是G中最大Menger集的頂點數，記為。
引理1 如果G是一個森林, 則G是Menger圖。
引理2 設S是G的一個獨立集，
如果對任意的
, 我們有
定理對任一偶圖
，有。
證 設S是G的最大獨立集使得
儘可能大，令
論斷 若Y0非空，則Y0的每一個頂點都是H的孤立點。
否則，必存在
和
使得
。由T的定義，
的每一個頂點在G中都不與x 相鄰，因此
仍然是G的一個最大獨立集，但這與S的定義矛盾。
論斷
是空集。
否則，
是G中比S 更大的獨立集，與S 的定義矛盾。
注意到T的定義，上面的討論意味著H是一個森林。由引理1，H是Menger圖，於是
S 是
的Menger集。由引理2，S也是G的Menger 集。因此，
，另一方面，由的定義易知
，定理得證。
