logo
推荐语:

一道一笔画问题(欧拉路径)的变式

作者:

慕容玖

TOP龙虎榜
暂无数据
TOP魅力榜
暂无数据
TOP火花榜
暂无数据

糖果路线图

阅读(106)
图论 一笔画
收录于老少皆宜 -- 2021年10月05日

从任意一个顶点出发,经过尽可能多的边(但不能重复),收集糖果,怎么走才能拿到最多的糖果?

展开正文...

前往题库

六一儿童节游园活动,如图所示是一个“糖果路线图”,其中顶点表示教室,边表示教室之间的路,糖果上的数字是经过每条边时可以拿的糖果数,小朋友可以从任意一个教室出发,走过每个教室,但不能走重复的路,那么小朋友最多能拿到__________颗糖果.

fzcpwXlDFB71Fff4LssujrV0FD7EiQF51

77

81

83

84

89

提交
23 人参与了问题讨论
    慕容玖

    这个问题就是一笔画问题,如图将图中的奇点标记为红色,共有4个. 由于能一笔画画出整个图形最多只允许有2个奇点(开始顶点和结束顶点),因此本题图不能一笔画.

    如果糖果数为5的边(糖果最少)被删除如下图所示: 这样就只剩下2个奇点,这样我们就可以一笔画出整个图形,从一个奇数点开始,在另一个奇数点结束.

    因此总糖果数为.

    • 5
    • 0
    • 评论(0)
    • 举报