已知图g至少要k笔才能画成，若去掉一条边后得图g′，问g′至少要几笔才能画成
答案:1 悬赏:20 手机版
解决时间 2021-11-14 11:23
- 提问者网友：辞取
- 2021-11-13 22:17
已知图g至少要k笔才能画成，若去掉一条边后得图g′，问g′至少要几笔才能画成
最佳答案
- 五星知识达人网友：怙棘
- 2021-11-13 23:48
G至少要k(k≥1)笔才能画，成去掉一边后得到G’ G’至少需要几笔画成？
则G中至少有2k个奇数度顶点，
若去掉边e=(u,v)的两个端点都是奇数，则G’至少 需要k-1笔画成
若去掉e的两个端点都是偶数度，则至少需要k+1 笔画成
若去掉e的两个端点一奇一偶，则G’至少需要k笔 画成
k=1时，去掉e的两个端点均为奇数时，则G’至少 需要1笔画成
其它情况同k>1
则G中至少有2k个奇数度顶点，
若去掉边e=(u,v)的两个端点都是奇数，则G’至少 需要k-1笔画成
若去掉e的两个端点都是偶数度，则至少需要k+1 笔画成
若去掉e的两个端点一奇一偶，则G’至少需要k笔 画成
k=1时，去掉e的两个端点均为奇数时，则G’至少 需要1笔画成
其它情况同k>1
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯