主题
Search

彼得森定理

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

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

CubicGraphWithNoPerfectMatching

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

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

另请参阅

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

使用 探索

参考文献

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. “彼得森定理。” 来自 —— 资源。 https://mathworld.net.cn/PetersensTheorem.html

主题分类