从一个角上的顶点,走遍图中的22条边,每条边（相邻两点间）的距离为1,请问怎么走的距离最短,可重复路线

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/07/08 09:17:26

先给各顶点编个号:
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为最小值.

按照平面几何原理,两点间直线距离最短.请问,在什么情况下,这条定理是错误的如图,∫1,∫2∫,3,∫4,是同一平面内的四条平行直线,且每相邻的两条平行直线间的距离均为h,正方形ABCD的四个顶点如图,正方形ABCD的四个顶点分别在四条平行线L1、L2、L3、L4上,这四条直线中相邻两条之间的距离依次为如图,L表示草原上的一条河.一少年从A出发,骑着马去河边,让马饮水,然后回村庄B.问怎么走,路线路程最短?请画出这条路线如图,L表示草原上的一条河,一少年从A出发,骑着马去河边,让吗饮水,然后回村庄B.问怎样走,路线路程最短?请画出这条路线 L1L2L3L4是同一平面内的四条平行直线,且每相邻的两条平行直线间的距离为h,正方形ABCD的四个顶点分别在这四条直线在“验证机械能守恒定律”的实验中,某同学重复做了4次实验,得到了4条纸带,4条纸带上两点间的距离如图，已知直线l1∥l2∥l3∥l4，相邻两条平行直线间的距离都是1，如果正方形ABCD的四个顶点分别在四条直线上，则s 如图,正方形ABCD的四个顶点分别在四条平行线l1、l2、l3、l4上,这四条直线中相邻两条之间的距离依次为h1、h2、已知如图，直线l1∥l2∥l3∥l4，相邻两条平行线间的距离都等于h，若正方形ABCD的四个顶点分别在四条直线上，求它的怎么求平面上到多边形顶点距离最短的点的坐标? 如图所示,一个平面内有四条直线L1,L2,L3,L4互相平行,相邻两条直线之间的距离为1