作业帮图形,绕课桌,至少多少距离
来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/05/05 07:37:22
图形,绕课桌,至少多少距离
如图,我拿两块来算,至少走八条边.三块,至少12条边.（可能没想到,求补充）
那么12块应该是12*4条边?
但是答案不是144.
如图,我拿两块来算,至少走八条边.三块,至少12条边.（可能没想到,求补充）
那么12块应该是12*4条边?
但是答案不是144.
答案应该是108.
这是一个经典的图论问题,叫做“中国邮路问题”.
我们先说答案,再证明这个是最小的.
请看上图.走法如下：
总的路线是红色路经,从A到S.如果遇到绿色环路,那么先走绿色环路,再接着走红色路径.
具体如下：
先从A点出发,一出发就遇到一个很长的绿色环路,所以先走绿色环路：
A→B→Q→R→C→D→S→P→A
然后顺着红色路径走：A→E→J
然后又遇到一个小的绿色环路,先走绿色环路：J→O→J
然后继续走完红色路径：J→F→K→O→T→S
计算长度：
不计算重复走的,图中总边数是：4*4+3*5=31
重复走了5条边：AB、CD、FK、JO、QR.
所以一共走了36条边,长度：36*3=108.
最后,我们用中国邮路问题的一些知识,证明这是最小的.
你可能听说过一个叫”哥尼斯堡七桥问题“的故事,我们就从这里开始.
一个图,如果有一个回路,该回路恰好经过每条边各一次,那么这个图叫欧拉图,这个回路叫欧拉回路.一个图有欧拉回路的充分必要条件是：每个顶点的度数都是偶数.
如果不要求是回路,也就是不需要返回起点,而只要求图中有一条道路,该道路恰好经过每条边各一次,那么这个道路叫欧拉道路.欧拉道路的充分必要条件是：除了起点和终点外,每个点的度数都是偶数.
比如：我们这个图中,顶点A的度数是2,因为有2条边（AB、AF）与A相连.
顶点B的度数是3,因为有3条边（AB、BC、BG）与B相连.
顶点G的度数是4,因为有4条边（BG、FG、GH、GL）与G相连.
我们这个图中,度数为奇数的顶点有10个：B、C、D、F、K、J、O、Q、R、S.
所以我们这个图既没有欧拉回路,也没有欧拉道路.
中国邮路问题,就是将原图加上一些边,使其有欧拉回路或欧拉道路.
具体到我们的图,我们的起点是A,于是就是要加上一些边,使得除了起点A和终点外,其他各个顶点的度数都变成偶数.加上的那些边,在实际应用中,就是重复走的路.
度数为奇数的顶点有10个,它们之中,除了一个作为终点的顶点可以是奇数度数外,其余9个必须变成偶数度.每添加一条边,可以将2个顶点变成偶数度,于是最少需要添加5条边,所以我们的方法是最少的.我们添加了5条边,也就是重复走的5条边：AB、CD、FK、JO、QR,将除了S外的其它9个顶点变为偶数度,将起点A和终点S变为奇数度.
这是一个经典的图论问题,叫做“中国邮路问题”.
我们先说答案,再证明这个是最小的.
请看上图.走法如下：
总的路线是红色路经,从A到S.如果遇到绿色环路,那么先走绿色环路,再接着走红色路径.
具体如下：
先从A点出发,一出发就遇到一个很长的绿色环路,所以先走绿色环路：
A→B→Q→R→C→D→S→P→A
然后顺着红色路径走：A→E→J
然后又遇到一个小的绿色环路,先走绿色环路：J→O→J
然后继续走完红色路径：J→F→K→O→T→S
计算长度：
不计算重复走的,图中总边数是：4*4+3*5=31
重复走了5条边：AB、CD、FK、JO、QR.
所以一共走了36条边,长度：36*3=108.
最后,我们用中国邮路问题的一些知识,证明这是最小的.
你可能听说过一个叫”哥尼斯堡七桥问题“的故事,我们就从这里开始.
一个图,如果有一个回路,该回路恰好经过每条边各一次,那么这个图叫欧拉图,这个回路叫欧拉回路.一个图有欧拉回路的充分必要条件是：每个顶点的度数都是偶数.
如果不要求是回路,也就是不需要返回起点,而只要求图中有一条道路,该道路恰好经过每条边各一次,那么这个道路叫欧拉道路.欧拉道路的充分必要条件是：除了起点和终点外,每个点的度数都是偶数.
比如：我们这个图中,顶点A的度数是2,因为有2条边（AB、AF）与A相连.
顶点B的度数是3,因为有3条边（AB、BC、BG）与B相连.
顶点G的度数是4,因为有4条边（BG、FG、GH、GL）与G相连.
我们这个图中,度数为奇数的顶点有10个：B、C、D、F、K、J、O、Q、R、S.
所以我们这个图既没有欧拉回路,也没有欧拉道路.
中国邮路问题,就是将原图加上一些边,使其有欧拉回路或欧拉道路.
具体到我们的图,我们的起点是A,于是就是要加上一些边,使得除了起点A和终点外,其他各个顶点的度数都变成偶数.加上的那些边,在实际应用中,就是重复走的路.
度数为奇数的顶点有10个,它们之中,除了一个作为终点的顶点可以是奇数度数外,其余9个必须变成偶数度.每添加一条边,可以将2个顶点变成偶数度,于是最少需要添加5条边,所以我们的方法是最少的.我们添加了5条边,也就是重复走的5条边：AB、CD、FK、JO、QR,将除了S外的其它9个顶点变为偶数度,将起点A和终点S变为奇数度.