跳至內容

塔特定理

維基百科,自由的百科全書
若移除正中央的頂點,則此分解成三個奇元件,故塔特定理推出此圖沒有完美匹配。(定理中,取為僅含該頂點的一元集。)

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