作业帮从一个角上的顶点,走遍图中的22条边,每条边（相邻两点间）的距离为1,请问怎么走的距离最短,可重复路线
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 13:44:45
从一个角上的顶点,走遍图中的22条边,每条边（相邻两点间）的距离为1,请问怎么走的距离最短,可重复路线
从一个角上的顶点,走遍图中的22条边,每条边（相邻两点间）的距离为1,请问怎么走的距离最短,可重复路线
从一个角上的顶点,走遍图中的22条边,每条边（相邻两点间）的距离为1,请问怎么走的距离最短,可重复路线
先给各顶点编个号:
0 1 2 3 4
5 6 7 8 9
a b c d e
不妨设起点为0.
对于一种遍历了所有的22条边的走法, 某些边会重复, 将这些重复的边也加入图中.
举个例子, 假如2-3之间的边走了4次, 就在2-3之间再连3条线, 并定义这三条边的长度都是1.
经过这样的处理, 可以通过添加一些边, 使一种走法变为无重复遍历(添加后的)所有边的走法.
于是问题化为: 最少添加多少条长为1的边, 能使该图能够从0出发, 无重复遍历所有边(一笔画).
Euler的定理说: 一个图能够一笔划当且仅当度数为奇数的顶点个数为0或2.
且当个数为2时, 必须以其中一个为起点, 以另一个为终点.
原图有8个度数为奇数的顶点(1, 2, 3, 5, 9, b, c, d), 且起点0的度数为偶数.
每添加一条长为1的边, 将使相邻的两个顶点的度数加1, 奇偶性改变.
添加一条边只能改变两个顶点的奇偶性.
分两种情况.
1. 如果要使所有顶点的度数变为偶数.
粗略估计, 可知至少要添加4条边.
稍加分析知4条边是不可行的, 因为这要求添加的每条边的两个端点都在1, 2, 3, 5, 9, b, c, d中.
然而5这个点不与1, 2, 3, 9, b, c, d中任何一个相邻, 以5为一端的边的另一端点不在其中.
于是这种情况至少需要添加5条边 (实际上9也一样, 因此至少6条).
2. 如果使添加后有两个顶点的度数为奇数, 且其中有一个是起点0.
粗略估计, 需要改变奇偶性的仍至少有8个点: 0以及1, 2, 3, 5, 9, b, c, d中的某7个.
因此至少要添加4条边.
然而4条边同样是不可行的, 因为这要求添加的每条边的两个端点都在0, 1, 2, 3, 5, 9, b, c, d中.
若9不为终点, 则需要添加以9为端点的边, 此时另一端点不在0, 1, 2, 3, 5, 9, b, c, d中.
9必须为终点, 于是c不为终点, 需要添加以c为端点的边, 另一端点只能为b或d.
无论是b, d中的哪一个, 以剩下的一个为端点的边的另一端点不在0, 1, 2, 3, 5, 9, b, c, d中.
这种情况至少需要添加5条边.
5条边可以做到的: 0-1, 2-3, 5-a, a-b, c-d即可.
由此得到走法(不唯一): 0-1-0-5-a-b-a-5-6-1-2-7-6-b-c-7-8-3-2-3-4-9-8-d-c-d-e-9.
长度22+5 = 27为最小值.