第92题:哥尼斯堡七桥问题
图:数学中,由有限个点和连接这些点的线所组成的图形叫做图。图中的点叫做图的 结点,连接两结点的线叫做图的 边。
一笔画:从图的一点出发,笔不离纸,不重复的遍历每条边恰好一次。
先阅读一下:哥尼斯堡七桥问题 及 欧拉定理。
下图是某展览厅的平面图,它由五个展室组成,任两个展室之间都有门相通,整个展览厅还有一个进口和一个出口,问游人能否从入口进一次不重复地穿过所有的门,然后从出口出?
解:
可将问题转化成图及一笔画问题,给每个房间编号并简化为图,如下,(2)中每一个结点都是偶结点,根据欧拉定理,能一笔画连通。