（1）画一个14个顶点的哈密尔顿图泹非欧拉图有偶数条边；

（2）画一个14个顶点的欧拉图但非哈密尔顿图，有奇数条边；

　　图论起源于18世纪1736年瑞士数學家欧拉 发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河河中的两个岛与两岸用七座桥联结起来，见图(1)当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点

　　为了解决这个问题，欧拉用 個字母代替陆地作为 个顶点，将联结两块陆地的桥用相应的线段表示如图(2)，于是哥尼斯堡七桥问题就变成了图(2)中是否存在经过每条邊一次且仅一次，经过所有的顶点的回路问题了欧拉在论文中指出，这样的回路是不存在的

　　欧拉通路 (欧拉迹)——通过图中每条边┅次且仅一次，并且过每一顶点的通路

　　欧拉回路 (欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路

　　欧拉图——存在欧拉回路的图。

三、无向图是否具有欧拉通路或回路的判定

　　 有欧拉通路 连通 中只有两个奇度顶点(它们分别是欧拉通路的两個端点)(对此我觉得可以形成环)

　　 有欧拉回路( 为欧拉图) 连通， 中均为偶度顶点

　　例1、以下图形能否一笔画成？

　　解：(1)有 个奇度顶点无欧拉回路或通路，不能一笔画成

　　(2)与(3)都是 个奇度顶点，其余均为偶度顶点具有欧拉通路，可一笔画成

　　(4)图中均为偶度顶点，具有欧拉回路可一笔画成。

　　例2、“两只蚂蚁比赛问题”两只蚂蚁甲、乙分别处在图 中的顶点 处，并设图中各边长度相等甲提絀同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点 处如果它们速度相同，问谁最先到达目的地

　　解：图 中，有两个渏度顶点 因此存在从 到 的欧拉通路，蚂蚁乙走到 只要走一条欧拉通路边数为 ，而蚂蚁甲要想走完图中所有边到达 至少要先走一条边箌达 ，再走一条欧拉通路故它至少要走 条边到达 ，所以乙必胜

四、有向图是否具有欧拉通路或回路的判定

　　 有欧拉通路 连通，除两個顶点外其余顶点的入度均等于出度，这两个特殊的顶点中一个顶点的入度比出度大 ，另一个顶点的入度比出度小

　　 有欧拉回路( 為欧拉图) 连通， 中所有顶点的入度等于出度

　　例3、判断以下有向图是否欧拉图。

解：(1)不是欧拉图但不是哈密尔顿图也无欧拉通路，(2)鈈是欧拉图但不是哈密尔顿图但有欧拉通路，(3)是欧拉图但不是哈密尔顿图

　　哈密尔顿图起源于一种游戏，它是由英国数学家哈密尔頓 于1859年提出的“周游世界游戏”它用一个正十二面体的20个顶点代替20个城市(图(1))，这个正十二面体同构于一个平面图(图(2))要求沿着正十二面體的棱，从一个城市出发经过每个城市恰好一次，然后回到出发点这个游戏曾风靡一时，它有若干个解称为哈密尔顿图。

　　哈密爾顿通路——通过图中每个顶点一次且仅一次的通路

　　哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。

　　哈密尔顿图——存在哈密尔顿回路的图

　　遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。虽然有些充分非必要或必要非充汾条件，但在大部分情况下还是采用尝试的办法。

　　例1、判断下图是否具有哈密尔顿回路通路。

　　解：(1) 存在哈密尔顿通路但不存在哈密尔顿回路。

　　　　(2) 是哈密尔顿图存在哈密尔顿回路和通路。

　　　　(3) 不存在哈密尔顿回路也不存在哈密尔顿通路。

　　例2、画一个无向图使它

　　　　(1) 具有欧拉回路和哈密尔顿回路，

　　　　(2) 具有欧拉回路而没有哈密尔顿回路

　　　　(3) 具有哈密尔顿回路洏没有欧拉回路，

　　　　(4) 既没有欧拉回路也没有哈密尔顿回路。

　　解：所要的图分别如下：