主題
Search

門格爾 n-弧定理


G 為一個 ,其中 AB 是兩個不相交的 n 元組 圖頂點。則要麼 G 包含 n 條兩兩不相交的 AB 路徑,每條路徑連線 A 中的一個點和 B 中的一個點,要麼存在一個少於 n圖頂點 的集合,該集合分隔 AB

Harary (1994, 第 47 頁) 將該定理表述為“分隔兩個不相鄰點 st 的最小點數等於不相交 s-t 路徑的最大數目。” Skiena (1990, 第 178 頁) 將該定理表述為“一個圖是 k-連通圖 當且僅當 每對頂點至少由 k 條頂點不相交的路徑連線”(Menger 1927, Whitney 1932)。


另請參閱

k-連通圖

使用 探索

參考文獻

Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1994.Menger, K. "Zur allgemeinen Kurventheorie." Fund. Math. 10, 95-115, 1927.Menger, K. 曲線理論。 Leipzig, Germany: Teubner, 1932.Skiena, S. 實現離散數學:使用 Mathematica 的組合數學和圖論。 Reading, MA: Addison-Wesley, 1990.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

在 上被引用

門格爾 n-弧定理

以此引用

Weisstein, Eric W. “門格爾 n-弧定理。” 來自 Web 資源。 https://mathworld.tw/Mengersn-ArcTheorem.html

主題分類