主题
Search

门格尔 n-弧定理

设 G 为一个 图，其中 A 和 B 是两个不相交的 n 元组 图顶点。则要么 G 包含 n 条两两不相交的 AB 路径，每条路径连接 A 中的一个点和 B 中的一个点，要么存在一个少于 n 个 图顶点 的集合，该集合分隔 A 和 B。

Harary (1994, 第 47 页) 将该定理表述为“分隔两个不相邻点 s 和 t 的最小点数等于不相交 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-弧定理。” 来自 MathWorld-- 资源。 https://mathworld.net.cn/Mengersn-ArcTheorem.html

主题分类