文档介绍：Liaoning Normal University
（2013届）
本科生毕业论文(设计)
题目：欧拉图在生活中的应用
学院：数学学院
专业：数学与应用数学
班级序号： 11班22号
学问题中，如果桥更多，那么“列举法”就无使用价值了，因此他放弃了这个方法，后来他改变了思考的角度，发现七桥问题仅仅涉及物体的位置关系，而与路程无关，于是他用点、表示岛屿，点、表示河的两岸，用连接两点的线表示桥，这样就可以画出如图1-1所示的无向图，这个问题就转化为“能否一笔画出该无向图且最后返回起点”。哥尼斯堡城七桥问题是否有解，就相当于这个无向图是否存在经过图中每条边一次且仅一次的简单回路。
我们知道，从某一个点出发最后又回到这个点，经过这一点的边的条数一定是偶数；经过中间的每一点，有进去的一条边，又有出来的一条边，因此，经过这些点的边的条数也是偶数。根据这个道理，我们可以看到图中经过每一点巧妙地解决了这个困扰人们多年但又十分有趣的问题。那这个方法也就成了我们现在学习的欧拉图的判定方法。
图1-1
1﹒2定义
定义1 图：图论中将图定义为一个偶对，其中表示顶中点的集合，是无序组集合的一个子集合，集合中的元素在出现不止一次边的集合。分别
用和表示图的顶点集合与边的集合。如果和都是有限集合，则称为有限图，否则称为无限图。若，则称为阶图。
定义2 平凡图：只有一个顶点的图叫做平凡图。
定义3 关联：一条边的端点称为与这条边关联。
定义4 连通：设是图中的两个顶点，若中存在一条道路，则称顶点和是连通的。
定义5 度：设中与顶点关联的边的数目，称为（在中）的度，记作。
定义6 回路：设为图，中顶点与边的交替序列…称为到的通路，若，则称通路为回路。（若的所有边各异，则称为简单回路。）
定义7 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。
定义8 给定有向图，经过中每边一次且仅一次的有向迹称为有向欧拉图；经过中每边一次且仅一次的有向闭迹(回路)称为有向欧拉回路。
定义9 含欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图，统称为欧拉圈。
定义10 欧拉闭迹：经过图的每条边恰好一次的闭迹。
定义11 欧拉迹：经过每条恰好一次的迹。
2欧拉图的判定定理和实例
2﹒1欧拉图的判定定理
下面介绍欧拉图的一些判定定理：
引理：设一般图，如果它的每个顶点的度数都是偶数，则的每条边都属于一条闭迹，因而也属于一个圈。
证明：利用下面的算法，可以找到一条包含任意指定边的闭迹。在该算法中，我们要构造一个顶点集和一个边集。
求闭迹的算法
令
令
令
当时，执行
找出一个不在中的边。
将放人中（也许已在中）。
将放入中。
令。
这样，经过i)～iii)步初始化以后，在算法中的，我们都要找到一条新边，它邻接于最后一次放入中的顶点，再将和分别放入和中，，直到最终又到达为止。
假设只要时，满足iv)a)的一条边总存在。设的终值它为，所产生的顶点集，边的多重集，于是，根据算法得到的就是包含初始边的一条闭迹。因此，我们只需证明：如果，那么就有一个不在中的边与邻接。正是在这里，用到了偶度次顶点的假设。
容易看到：算法中每步iv)的d)结束时，一般图的每个顶点都具有偶度次，只有顶点（它起始于奇度1）和最新加入的顶点（它的度数刚刚增加1）可能除外。此外，和具有偶度次，当且仅当，因此，如果，则在一般图中就具有奇度次。既然在一般图中具有偶度次，则必存在一个还不属于的边与邻接。所以，当算法结束时，必有，从而式是一条闭迹。
由于一条闭迹中的边可以被划分为圈，所以我们完成了引理的证明。
定理1 设是一个连通一般图，则中存在闭欧拉迹，当且仅当中每个顶点的度数是偶数。
证明：我们已经观察到了：如果中有一条闭欧拉迹，则的每个顶点都具有偶度次。现在设是一个连通一般图，且它的每个顶点都具有偶度次，我们选定的任意一条边，并应用引理证明中给出的求闭迹的算法，求得一条包含边的闭迹。令是去掉中属于闭迹的边后得到的一般图，则的所有顶点都具有偶度次。如果中至少含有一条边，则由于的连通性，中至少有一条边与闭迹中的某个顶点邻接，我们对和边应用算法求出一条包含边的闭迹。现在我们把和在顶点处拼接在一起，得到一条包含和的所有边的闭迹。令是中去掉的边后得到的一般图，如果中至少含有一条边，则它必有一条边与闭迹中的某个顶点邻接，再对和边应用算法，求得一条包含边与闭迹，又将和在顶点出拼接，得到一条包含，和的所有边的闭迹。重复上述过程，直到所有的边都包含在一条闭迹中为止。因此，重复