图论题：证明：一颗树最多只有一个完美匹配。

显示全部楼层 · 2011-6-7 12:54:58

这就是完整的题目了。

千问 · 2011-6-7 12:54:58

对每个叶子结点，它只能和唯一与它相邻的那个点匹配如果一个结点连了两个或以上的叶子结点，那么这两个叶子结点中至少有一个是不能匹配的所以，只有当每个结点最多只和一个叶子结点相邻的时候，才会存在完美匹配去掉叶子结点以及与其相邻的点，会得到若干不连通的树重复上面的过程，直到所有的结点都被匹配或者有点不能被匹配由于在任意阶段，每个结点最多只会和一个叶子结点相连，所以这个匹配的方法都是被唯一确定下来的因此一棵树最多只有一种完美匹配的方法。...

千问 · 2011-6-7 12:54:58

用反证法。假设存在2个完美匹配M和M’，则作M和M‘的对称差，其中会有交错圈，与树的定义矛盾。证毕。...