问答题
试问:从前两题的图G
1
,G
2
的任一点出发,能否走遍该图的各边且仅过每边一次而回到出发点,若能则找出一条这样的路。
【正确答案】
类似于哥尼斯堡七桥问题,在一个图中存在从任意一点出发走遍该图的各边且仅过每边一次而回到出发点的回路的充要条件是图中无奇点。
考察G
1
各点均为偶点,即存在此类回路,其中一条为
μ=v
1
v
2
v
4
v
6
c
5
v
3
v
4
v
5
v
2
v
3
v
1
考察G
2
各点v
2
,v
3
,v
4
,v
5
均为奇点,故不存在此类回路。
【答案解析】
提交答案
关闭