塔特定理

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