图特定理

This article "图特定理" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:图特定理. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This article "图特定理" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:图特定理. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

在图论中，图特定理（Tutte's Theorem）说：

图G有完美匹配（1–因子）当且仅当对所有的子集 $U\subset V(G)$，有 $q(G-U)\leq |U|$。

$q(X)$表示 $X$的奇数元件数量（有奇数顶点的连通元件）。

这定理以William Thomas Tutte命名，是赫尔婚姻定理的推广，也是Tutte–Berge公式的特例。

证明

Diestel的证明在 http://diestel-graph-theory.com/Chinese/ChineseSample5.pdf （p. 39）

另看

• 二分匹配
• 彼得森定理（用图特定理）

以下都是图特定理的特烈：

• 赫尔婚姻定理
• 柯尼希定理

参考文献

This article "图特定理" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:图特定理. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• 库拉托夫斯基定理
• 惠州市人民代表大会
• 黑暗浪潮
• 王诗龄
• 汪聪
• 詹姆士·弗雷德里克·埃利奧特
• 怪獸與牠們的產地5

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

<addthis />