图论答案2023秋

第四章测试

1.设M和N是简单图G的两个不同的完美匹配，则由M与N的对称差在G中的边导出子图的每个连通分支必为（ ）.
A:奇数个顶点的路 B:偶数个顶点的圈 C:奇数个顶点的圈 D:偶数个顶点的路
答案:B
2.一棵树T可以有两个或者两个以上的完美匹配.（ ）
A:错 B:对 3.2n个顶点的完全图中不同的完美匹配个数为（ ）.
A:(2n)!! B:(2n-1)! C:(2n-1)!! D:(2n)! 4.如果每个小伙子恰好认识k个姑娘，而每个姑娘也恰好认识k个小伙子(k > 0)，则每个小伙子都能与自己认识的姑娘结婚.（ ）
A:错 B:对 5.
本题中所示图没有完美匹配.（ ）
A:错 B:对