下载APP
【简答题】
给出彼得松图的一个边子集,使它既是最小边覆盖集、又是最大匹配,并求其匹配数β
1
和边覆盖数α
1
。
题目标签:
最大匹配
边覆盖数
彼得松图
举报
如何制作自己的在线小题库
参考答案:
参考解析:
刷刷题刷刷变学霸
举一反三
【判断题】一个图若存在完美匹配,则完美匹配一定为最大匹配
A.
正确
B.
错误
查看完整题目与答案
【简答题】设G为无孤立点的无向简单图,M既是G中的最大匹配,又是G中的最小边覆盖集,则M应为()匹配。
查看完整题目与答案
【判断题】彼得松图10阶3-正则图。
A.
正确
B.
错误
查看完整题目与答案
【简答题】无向图G如图所示,求G中两个不同的极小边覆盖集,一个最小边覆盖集及边覆盖数α1。
查看完整题目与答案
【简答题】彼得松图即不是欧拉图也不是哈密顿图。至少加几条新边才能使它成为欧拉图?又至少加几条新边才能使它变成哈密頓图?
查看完整题目与答案
【简答题】证明:彼得松图的边色数X’=4。
查看完整题目与答案
【判断题】设G = 中无孤立点,|V|=n,则边覆盖数 + 匹配数 = n
A.
正确
B.
错误
查看完整题目与答案
【判断题】设G = V1, V2, E为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配,也是最大匹配。
A.
正确
B.
错误
查看完整题目与答案
【简答题】证明彼得松图的边色数x’=4。
查看完整题目与答案
【判断题】设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配,也是最大匹配。
A.
对
B.
错
查看完整题目与答案