塔特定理

图论中,塔特定理(英语:Tutte theorem)是:[1]

若移除正中央的顶点,则此分解成三个奇元件,故塔特定理推出此图没有完美匹配。(定理中,取为仅含该顶点的一元集。)

匹配当且仅当

其中 是图的奇数元件的数量(有奇数个顶点的连通元件)。

相关

阅读

  • Bondy, J. A. Graph theory with applications. New York: American Elsevier Pub. Co. 1976. ISBN 0-444-19451-7 (俄语). 
  • Lovász, László. Matching theory. Amsterdam: North-Holland. 1986. ISBN 0-444-87916-1 (俄语). 

参考文献

  1. ^ Diestel, Reinhard. Graphentheorie. 2010. doi:10.1007/978-3-642-14912-2.