主題
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.tw/PetersensTheorem.html

主題分類