迷宫专题汇总

迷宫的历史

迷宫的分析1

迷宫的分析2

迷宫的分析3

迷宫游戏1

迷宫游戏2

迷宫游戏3

迷宫——另外的声音

　　迷宫的分析3

　　图论的基本概念 这里概念有的叙述不够严密，请参考图论专著或教材，例如乔维声的《离散数学》。

　　图（ Graph ） 含有两个集合，一个集合是结点集合，必须非空，其中元素称作结点；另一个是边的集合，其中元素称作边，可以是空集合，每个边必须关联于两个点。

　　结点的度：关联的边数。

　　孤立点，悬挂点

　　路：点与边的交替序列 v0，e1，v1 ， e2，，v2，……，ek，vk ，其中边与其前后的点相关联。

　　回路：始点终点相同的路。

　　两点的连通：存在路 v0，e1，v1 ， e2，，v2，……，ek，vk ，则称 v0，vk 连通。

　　图的连通：图中任何两点连通。

　　欧拉路：经过图中每边恰好 1 次的路。

　　欧拉回路：经过图中每边恰好 1 次的回路。

　　欧拉图：无孤立点且有欧拉回路的图。

　　欧拉定理 1 连通图是欧拉图的充要条件是图的每个结点的度数都是偶数。

　　求欧拉图的一条欧拉回路的方法：由任何一点出发，经与之关联的且尚未走过的边到另一点，如此进行，直到回到出发点。

　　欧拉定理 2 连通图具有连接图中两点的欧拉路，当且仅当这两点是图中仅有的奇度数点。

　　求两点间欧拉路的方法：由两点中任何一点出发，经与之关联的且尚未走过的边到另一点，如此进行，直到回到所给的另一点。

　　一笔画问题

　　例 一幢房子有 5 个房间，其中两个有通向外面的门，称前门与后门。其他房间也有门相连如图。如何由前门进经过所有的门恰 1 次最后由后门出？

　　解法1 左图，找欧拉路。

　　解法2 右图，找欧拉回路。