تسجيل الدخول

تسجيل

Menger,s n-Arc Theorem

المؤلف:  المرجع الالكتروني للمعلوماتيه

المصدر:  www.almerja.com

الجزء والصفحة:  ...

18-3-2022

3011

Menger's n-Arc Theorem

Let  be a graph with  and  two disjoint -tuples of graph vertices. Then either  contains  pairwise disjoint -paths, each connecting a point of  and a point of , or there exists a set of fewer than  graph vertices that separate  and .

Harary (1994, p. 47) states the theorem as "the minimum number of points separating two nonadjacent points  and  is the maximum number of disjoint  paths." Skiena (1990, p. 178) states the theorem as "a graph is k-connected graph iff every pair of vertices is joined by at least  vertex-disjoint paths" (Menger 1927, Whitney 1932).