图论教程.pptVIP

第七部分 图论方法 第十二章 图论方法 1. 图的基本概念 图是一个有序对V，E，V是结点集，E是边集； 无向边，与无序结点对(v, u)相关联的边； 有向边，与有序结点对v, u相关联的边； 无向图，每条边都是无向边的图； 有向图，每条边都是有向边的图. 图的基本概念 混合图，既有有向边，也有无向边的图. 平凡图，仅有一个结点的图； 零图，边集为空集的图V, ?，即仅有结点的图. 自回路(环)，关联于同一个结点的边. 无向平行边，联结相同两个结点的多于1条的无向边； 有向平行边，联结两个结点之间的多于1条且方向相同的有向边； 简单图，不含平行边和自回路的图. 图的基本概念 在有向图D＝V,E中，以v(?V)为起点的边之条数为出度deg＋(v)；以v(?V)为终点的边之条数为入度deg－(v). 在无向图G＝V,E中，与结点v(?V)关联的边数，即为结点度数deg(v)或d(v)；在有向图中，结点v的出度和入度之和为度数. 最大度数，?(G)＝max{deg(v)?v?V}；最小度数，?(G)=min{deg(v)?v?V} 图的基本概念 有n个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。 设G＝V,E, V，E的子集V?,E?构成的图G?=V?,E?是图G的子图；若G??G且G??G，(V??V或E??E)，G?是G的真子图. 生成子图，设图G＝V,E, 若E??E, 则图V,E?是图V,E的生成子图，即结点与原图G相同的子图. 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路； 通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路； 具有欧拉回路的图称为欧拉图； 具有欧拉通路但无欧拉回路的图称为半欧拉图。 2. 哥尼斯堡七桥问题 判别方法： (1) 无向连通图是欧拉图当且仅当其所有顶点的度数都是偶数； (2) 无向连通图是半欧拉图当且仅当其奇点数为2； 2. 哥尼斯堡七桥问题 Fleury算法： 任取v0∈V(G)，令P0=v0； 设Pi=v0e1v1e2…ei vi已经行遍，按下面方法从中选取ei+1： （a） ei+1与vi相关联； （b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c）当（b）不能再进行时，算法停止。 2. 哥尼斯堡七桥问题 例 3最短路径问题 单源点的最短路径问题：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。 3最短路径问题 3最短路径问题 3最短路径问题 Dijkstra 算法 (1)假设用带权的邻接矩阵A来表示带权有向图，A[i][j]表示弧vi，vj上的权值。若vi，vj不存在，则置A[i][j]为∞。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。设D[i]从v出发到图上其余各顶点（终点）vi可能达到的最短路径长度的初值。 (2) 选择结点，使得 , vj就是当前求得的一条从v出发的最短路径的终点。令S＝SU{vj}. (3) 修改从v出发到集合V－S上任一顶点vk可达的最短路径长度。如果D[j]+A[j][k]D[k], 则修改D[k]为D[k]=D[j]+A[j][k]. (4) 重复操作（2）（3）共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。 4．中国邮递员问题 一个邮递员从邮局出发投递信件，他必须在他所管辖范围内的所有街道至少走一次，最后回到邮局，他自然希望一条最短的路线完成投递任务，那么如何选择这样的路线呢？ 构造无向带权图G=V,E,W，E为街道集合，V中元素为街道的交叉点。街道的长度为该街道对应的边的权，显然所有权大于0。邮递员问题就变成了求G中一条经过每条边至少一次的回路，使该回路所带权最小的问题。满足以上条件的回路是最优投递路线或最优回路。 4．中国邮递员问题 C是带正权无向连通图中的最优投递路线当且仅当对应的欧拉图应满足： G的每条边在中至多重复出现一次； G的每个圈上在中重复出现的边的权之和不超过该圈权的一半。 4．中国邮递员问题 算法步骤如下： (1)若G中无奇点，令G*=G，转2，否则转3； (2)求G*中的欧拉回路，结束； (3)求G中所有奇点对之间的最短路径； (4)以G中奇点集V’为顶点集，边(vi,vj)的权为之间最短路径的权，得完全带权图K2k； (5)求K2k中最小权完美匹配M； (6)将M中边对应的各最短