图论中几个典型问题

1、图论中几个典型问题的算法及其Matlab实现 图论的产生与发展 1.格尼斯堡七桥问题 哥尼希堡城有一座横贯全市的普雷格尔 河，河中有两个岛屿，两岸及岛屿有七座桥相连，如图(1)2.四色问题3.哈密尔顿周游世界问题第一节 图的基本概念 1.图的定义 图由一些点和点之间的连线所组成。 用V=v1,v2,表示全体顶点的集合，用E=e1,e2,表示所有边的集合，如果对于E中任一条边，在V中都有一对定点(vi,vj)和它对应，则称由V和G组成的集体为一个图，记为G=(V,E),简记为G。 2.基本概念 关联：如果顶点v是边e的一个端点，则称边e和顶点v相关联。 邻接：对于顶点u和v，若(u,v)属于E，

2、则称u和v是邻接的，对于两条边，若有共同的顶点，则称这两条边是邻接的。 阶：图中顶点的个数。 度：与图中某个顶点关联的边的个数，称为该顶点的度。 环：两个端点重合的边。 多重边：关联于同一对顶点的两条或两条以上的边。 简单图：没有环也没有重边的图。 途径：图G=(V,E)的一个点和边交替出现的有限非空序列。 迹：一条没有重复边的途径。 路：一条各顶点互不相同的途径。 闭途径：起点与终点相同的途径。 闭迹：起点与终点相同的迹。 圈(回路)：起点与终点重合的路。 连通：若顶点u和v之间存在一条路，则称u和v连通。 连通图：任意两个顶点都连通的图。 完全图：任意两个顶点之间都有一个顶点相连的简单图

3、桥(割边)：设G是连通图，若从G中删除边e后，图不再连通，则称边e为图G的桥(割边)。 无向图：每条边都没有方向的图。 有向图：每条边都有方向的图。 赋权图：在图的每条边上标明了数量关系，可能是距离、时间、费用、电阻等等，这些数值称为相应边的权，边上带权的图称为赋权图。同时称带权的有向图为网络。 子图：设有两个图G=(V,E),G1=(V1,E1),若V1是V的子集，E1是E的子集，则称G1是G的子图。 第二节 图的矩阵表示 要将图的信息存到计算机中，需要使用专门设计的数据结构，比较常见的是邻接矩阵、前向星、邻接表、链式前向星这四种方式。此外还有结构比较复杂的十字链表方式。 无向图的关联矩阵：

4、设图G=(V,E)的顶点集和边集分别为V(G)=v1,v2,vn ,E(G)=e1,e2,em，用Bij表示顶点vi与边ej关联的次数，把行对应顶点，列对应边的矩阵B(G)=(bij)nm称为图G的关联矩阵。 无向图的邻接矩阵：设图G=(V,E)的顶点集为V(G)=v1,v2,vn ，用aij表示G中顶点vi与vj之间的边数，则n阶方阵M(G)=(aij)nn称为G的邻接矩阵。 无向赋权图邻接矩阵的定义：设图G=(V,E)的顶点集为V(G)=v1,v2,vn，其邻接矩阵为n阶对称阵A，元素定义为aii=0,当顶点vi与vj之间没有连线时，aij=inf，当顶点vi与vj之间有连线时，aij=边

5、vivj的权值。 例：写出下图的邻接矩阵 有向图的关联矩阵：设图G=(V,E)的顶点集和边集分别为V(G)=v1,v2,vn ,E(G)=e1,e2,em，则矩阵B=(bij)nm为有向图G的关联矩阵，其元素定义为，bij=1,顶点vi是边ej的起点； bij=-1,顶点vi是边ej的终点； bij=0,顶点vi是边ej不关联； bij=-2，ej为环，且关联与vi。例：写出下图的关联矩阵 有向图的邻接矩阵：设图G=(V,E)的顶点集为V(G)=v1,v2,vn ，用aij表示G中以顶点vi为起点与以vj为终点之间的边数，则n阶方阵M(G)=(aij)nn称为G的邻接矩阵。 有向赋权图邻接矩阵

6、的定义：设图G=(V,E)的顶点集为V(G)=v1,v2,vn，其邻接矩阵为n阶矩阵A，元素定义为,当起点vi与终点vj之间没有连线时，aij=inf，当起点vi与终vj之间有连线时，aij=边vivj的权值。第三节 几个典型问题 1.最短路径问题 实际问题：给定连接若干城市的铁路网，找一条给定两城市间的最短线路。 最短路径定义：在赋权图G=(V,E)中，设顶点vi,vj是图的两个顶点，从顶点vi到vj的路径长度定义为路径上各条边的权值之和，从顶点vi到vj的所有路径中，其中路径长度最小的一条路径。 重要性质：最短路是一条路径，且最短路上任一段也是最短路。求单源最短路径的Dijkstra算法

7、算法描述： (1)算法思想：设G=(V,E)是一个赋权有向图，设集合S用来保存已求得最短路径的顶点序号，集合U为其余未确定最短路径的顶点集合，按照最短路径长度递增的次序依次把U中顶点加入S。 总之，从源点v到各个顶点层层推进过程中，要保证每一步走的都是最短路径。 (2)算法步骤： a.初始时，S只包含源点，S=v，U=其余顶点。 b.从U中选取一个顶点k，使dist(v,k)最短，把k加入S。 c.以k为新的中间点，对于U中顶点u，如果dist(v,k)+dist(k,u)fxy，则称f为最大流(Maximum Flow)，记为fmax。 运输网络中一个重要的问题是要找出它的一个最大流fmax

8、。 定义4：给定网络N=(V,A,C)是一个单源、单汇的网络，若V被分成两个非空子集S, ,使得源 ，称 是分离x和y的一个割集(Cut Set)。割集 中所有始点在S中，终点在 中的弧的容量之和，称为 的割集容量，记为 。割集容量最小的割称为最小割(Minimum Cut)。 例：在右图所示的网络中，选S=x,v3,v4, ，则(x,v1),(v3,y),(v4,y)是N的一个割集，割集容量为 =4+2+3=9。 如选S=x, 则(x,v1),(x,v3),(x,v4) 也是N的一个割集，此时割集容量为11. 并且，在任何网络中，最大流的流量等于最小割集的容量 定义5：设f是网络N中的一个可

9、行流，P是一条xy路，则P满足下列两个条件之一的弧(vi,vj)称为增广弧(Incrementing Arc)。 a. ，且fij0。 如果P中的弧都是增广弧，则P是关于f的增广路(Incrementing Path)。并且若N中有一f增广路P，则f不是最大流。如图，(x,y)-路xv2v1v3y是f增广路求最大流问题的FF算法 最大流问题的算法思想： 首先从任何一个可行流(如零流)出发，判断网络N中是否有关于f的xy增广路。若没有这样的增广路，则f就是最大流；若有这样的增广路，则对f进行调整，得到一个新的流量更大的可行流f ；对f 再重复上述过程，直到找不出xy增广路为止。 算法关键与核心：

10、寻找xy增广路。算法步骤：(1)标号过程1).给源x以标号 (永久标号)。2).选择一个已标号的顶点vi，对vi的所有未给标号的邻接点作如下处理：a.若弧 ，且fij0，令 ， 并给vj以标号 。c.重复2)过程直到汇y被标号，或不再有顶点可标号为止。如果y得到标号，说明存在一条xy增广路，转步骤(2)调整过程；若y未获得标号，标号过程无法进行，这时，令S是所有标号点集，T是所有未标号点集，则(S,T)是一个割集，则割集(S,T)的容量就是最大流的流量。(2)调整过程a.令 ，调整增广路P中的流量如下：得到新的可行流f =fij，显然总流量为b.去掉所有标号，回到步骤(1)，重复上述过程，直到

11、无法进行为止，结束。 例：求下图所示的网络最大流 C=0 5 4 3 0 0 0 0; 0 0 0 0 5 3 0 0; 0 0 0 0 0 3 2 0; 0 0 0 0 0 0 2 0; 0 0 0 0 0 0 0 4; 0 0 0 0 0 0 0 3; 0 0 0 0 0 0 0 5; 0 0 0 0 0 0 0 0; 算法Matlab实现： q = 0 5 4 2 0 0 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 w = 11 e = 9 0 0 1 0 0 0 0