塔特定理

图论中,塔特定理(英語: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.