彼得森定理 -- 来自 Wolfram MathWorld

彼得森定理

彼得森定理指出，每个没有桥的立方图都有一个完美匹配（Petersen 1891; Frink 1926; König 1936; Skiena 1990, p. 244）。事实上，这个定理可以扩展为：“每个有 0、1 或 2 个桥的立方图都有一个完美匹配。”

上面的图显示了 3 个桥的最小反例，即一个在 16 个顶点上没有完美匹配的连通立方图。该图在 Wolfram 语言中实现为GraphData["Cubic", 16, 14].

Errera (1922) 通过证明如果连通立方图的所有桥都位于的单个路径上，则具有完美匹配，从而加强了彼得森定理。

另请参阅

桥, 立方图, 完美匹配, 塔特定理

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Errera, A. "Du colorage des cartes." Mathesis 36, 56-60, 1922.Frink, O. "A Proof of Petersen's Theorem." Ann. Math. 27, 491-493, 1926.König, D. Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe. 1936.Petersen, J. "Die Theorie der Regulären Graphen." Acta Math. 15, 193-200, 1891.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 244, 1990.

请引用为

Weisstein, Eric W. “彼得森定理。” 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/PetersensTheorem.html