【完美匹配】图论题:证明:一颗树最多只有一个完美匹配.这就是完整的题目了。_...
答案:2 悬赏:0 手机版
解决时间 2021-02-09 16:06
- 提问者网友：聂風
- 2021-02-09 13:03
【完美匹配】图论题:证明:一颗树最多只有一个完美匹配.这就是完整的题目了。_...
最佳答案
- 五星知识达人网友：渊鱼
- 2021-02-09 13:21
【答案】 对每个叶子结点,它只能和唯一与它相邻的那个点匹配
如果一个结点连了两个或以上的叶子结点,那么这两个叶子结点中至少有一个是不能匹配的
所以,只有当每个结点最多只和一个叶子结点相邻的时候,才会存在完美匹配
去掉叶子结点以及与其相邻的点,会得到若干不连通的树
重复上面的过程,直到所有的结点都被匹配或者有点不能被匹配
由于在任意阶段,每个结点最多只会和一个叶子结点相连,所以这个匹配的方法都是被唯一确定下来的
因此一棵树最多只有一种完美匹配的方法.
如果一个结点连了两个或以上的叶子结点,那么这两个叶子结点中至少有一个是不能匹配的
所以,只有当每个结点最多只和一个叶子结点相邻的时候,才会存在完美匹配
去掉叶子结点以及与其相邻的点,会得到若干不连通的树
重复上面的过程,直到所有的结点都被匹配或者有点不能被匹配
由于在任意阶段,每个结点最多只会和一个叶子结点相连,所以这个匹配的方法都是被唯一确定下来的
因此一棵树最多只有一种完美匹配的方法.
全部回答
- 1楼网友：西风乍起
- 2021-02-09 14:19
我学会了
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯