大连理工大学软件学院 离散数学 第七章 图论th.ppt

*/36 哈密尔顿图 已知的最好的求一个图里的哈密尔顿回路或者判定这样的回路不存在的算法具有指数的最坏情形时间复杂度（向对于图的顶点数来说）。找到具有多项式最坏情形时间复杂性的解决算法是NP复杂的。 */36 哈密尔顿图的应用 旅行商问题：一位旅行商想要访问n个城市中每个城市恰好一次，最后返回到出发点，并且走的路程最短。怎样设计路线？ */36 哈密尔顿图的应用 假定城市两两之间都直接连通，那么走法一共有(n-1)!种，但是考虑相反顺序构成的哈密尔顿回路是一样的，因此只需要检查(n-1)!/2条路径。 但是，假定有25个城市，则24！/2大约等于3.1*1023，这个数目非常大，因此遍历的做法不科学。 由于旅行商问题在实践和理论中都有重大的意义，因此已经投入了巨大的努力来解决这个问题，但是，还没有找到多项式最坏情形时间复杂度的算法。在实际中，当n的数目很多时，采用的是近似算法，找到一个近似解。 */36 作业 P155 1 离散数学 大连理工大学软件学院 回顾 路径，简单路径，基本路径 连通，强连通，单向连通，弱连通 分支 回路，半回路，有向回路 图的矩阵表示方法 邻接矩阵 可达矩阵 */36 */36 7.5欧拉图 哥尼斯堡七桥问题 ：从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？ 结点表示陆地区域，边表示桥。于是，哥尼斯堡七桥问题就是要找到左图中包含图的所有边的简单闭路径。 */36 欧拉图 对这个问题进行推广，也就是判断在一个多重图里是否存在包含每一条边的简单回路？ 1736年欧拉发表论文，在论文中提出了一条解决此问题的简单准则，确定七桥问题是不能解的。 */36 欧拉路径与欧拉闭路 定义：图G中包含其所有边的简单开路径称为图G的欧拉路径，图G中包含其所有边的简单闭路径称为G的欧拉闭路。 例：判断下列三个图中是否有欧拉路径或欧拉闭路。 */36 欧拉路径与欧拉闭路 例：判断下列三个图中是否有欧拉路径或欧拉闭路。 */36 欧拉图 定义：每个结点都是偶结点的连通无向图称为欧拉图。每个结点的出度和入度相等的连通有向图称为欧拉有向图。 （规定平凡图是欧拉图） 欧拉给出了一个连通无向图是欧拉图的充分必要条件，这就是下面的欧拉定理。 定理：设G是连通无向图，则G是欧拉图，当且仅当G有欧拉闭路。 */36 欧拉定理 定理：设G是连通无向图，则G是欧拉图，当且仅当G有欧拉闭路。 证：若连通无向图G有欧拉闭路，则从该闭路径中任选一个节点a，按照闭路径的顺序依次遍历节点。在路径上每访问一个节点就给该节点增加了两度。因此，每个节点的度都是偶数，该图是欧拉图。 再证必要性。对G的边数采用归纳法。 若G没有边，即图G是平凡图，必要性显然成立（这里把0当作偶数）。 */36 欧拉定理 令 ，设任意边数少于n的连通欧拉图有欧拉闭路。若G有n条边，由G是连通欧拉图知，它的任意结点的度大于1，可得G有回路，设G有长度为m的回路C，知在G中存在闭路径v0e1v1…vm-1emv0，其中v0,v1,…, vm-1互不相同，并且{v0,v1,…,vm-1}和 分别是C的结点集合和边的集合。令G=G-{e1,e2,…,em}，设G有k个分支G1,G2,…,Gk。由于G是连通的，G的每个分支与C都有公共结点。设 与C的一个公共结点为 ，我们还可以假定 。显然，Gi为边数少于n的连通欧拉图。根据归纳假设，Gi有一条从 至 的闭路经Pi。因此，以下的闭路经 就是G的一条欧拉闭路。 */36 欧拉定理 尼斯堡七桥问题，由于哥尼斯堡七桥问题不是欧拉图，不存在欧拉闭路，所以哥尼斯堡七桥问题无解。 */36 构造欧拉回路 构造欧拉回路的方法： 1、在图G中任选一个结点，找到一个基本循环a1，从G中删去a1的各边之后得到生成子图G1，G1中的每个结点仍然是偶结点； 2、如果G1是零图，则a1即为G中的欧拉回路，退出；否则，转3； 3、若G1不是零图，由G的连通性可知，G1中必有与a1有公共顶点的基本循环a2。这两个基本循环可以通过这个公共顶点合并成一个简单循环； 4、从G1中去掉a2的各边，得到一个生成子图，依次执行2和3，直到G1变为零图，就得到了一条包含各边的欧拉回路。 */36 构造欧拉回路 例：构造下图的欧拉回路。 */36 构造欧拉回路 解：首先找出一个基本圈C1，如v1v2v3 v1，从G中删去C1的各条边后得G1，再找出一个基本圈C2，如v1v4v5v1，把两个基本圈合并，得v1v2v3 v1v4v5v1。再从G1中删