图论基本概念

2012数学建模培训第6讲图论模型及Matlab程序“图论模型及其Matlab程序”学习内容1.如何理解图、无向图、有向图？2.如何理解顶点与顶点及边的关系？3.如何理解加权图？4.如何确定图的邻接矩阵和关联矩阵？5.如何确定网络的邻接矩阵？6.如何应用程序实现邻接矩阵和关联矩阵的转化？7.什么是最短路径问题，通常有几类？8.Dijkstra算法和Floyd算法各适用于哪一类最短路问题？9.如何应用程序实现Dijkstra算法和Floyd算法，怎样理解、改进输出结果？10.如何理解树、生成树、最小生成树？11.如何应用程序求解最小生成树？12.什么叫环游、最优环游、Euler环游、Hamilton环游、Euler图、Hamilton图？13.如何理解中国邮递员问题和旅行商问题间的区别？14.如何利用程序判定Euler图以及Hamilton图？15.如何理解网络流、网络最大流、最小费用最大流？16.如何应用Ford-Fulkerson算法、Dinic算法及Busacker-Gowan算法求解最大流、最小费用最大流？图论模型及其Matlab程序图论是数学的一个分支，以图为研究对象。图论中的图是由若干个给定顶点及若干条连接两个顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构，可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模，因此图论研究越来越得到这些领域的专家和学者的重视。

图论最早的研究起源于瑞士数学家欧拉，他在1736年成功地解决了哥尼斯堡七桥问题，从而开创了图论的先河。在此后的200多年时间内,图论的研究从萌芽阶段，逐渐发展成为数学的一个新分支。20世纪70年代以后，由于高性能计算机的出现，使大规模图论问题的求解成为可能。目前，图论理论已广泛应用于运筹学、计算机科学、电子学、信息论、控制论、网络理论、经济管理等领域。

由于图论有着丰富的算法和广泛的应用，所以一直以来图论问题在信息类竞赛中占有较大比重。例如，在著名的ACM/ICPC程序设计竞赛中,图的遍历、最小生成树、最短路径、网络流、匹配问题、图的连通性、图着色等都是常见问题。数学建模竞赛中的图论问题不及ICPC中的普遍，难度也不大。

本讲主要介绍图的一些基本概念及存储方法、最短路问题、最小生成树问题、可行遍性问题、网络流问题及其Matlab程序。本讲要求学生理解图论的基本概念；掌握图的邻接矩阵表示方法；能较为熟练地根据实际问题正确地建立图论模型，并利用相应的Matlab程序求解；不要求理解算法，编写程序。一、图的基本概念与图的存储1.图的基本概念

图论的一个特点就是概念特别多。这里只介绍一些基本的概念，其它概念在后面用到时再补充介绍。1.1图图是由顶点集合和边的集合组成的数据结构，通常用G(V,E)来表示，其顶点集合和边的集合分别用V(G)和E(G)表示。例如，右图所示的图可表示为G(V,E)。其中，V(G)={0,1,2,3,4,5}，E(G)={(0,1),(0,2),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4)}。1.2无向图与有向图所有边都没有方向的图称为无向图，如1.1中的图；每条边都有方向的图称为有向图，通常用<u,v>表示从u到v的有向边。例如，对于右图所示的有向图G(V,E)，V(G)={0,1,2,3,4,5,6},E(G)={<0,1>,<1,2>,<1,4>,<1,5>,<2,4>,<3,2>,<4,1>,<4,3>,<5,6>}。1.3完全图任何一对顶点都有一条边的图称为完全图；任何一对顶点u,v都有<u,v>和<v,u>两条有向边的图称为完全有向图。例如，左图为完全图，右图为完全有向图。1.4顶点与顶点、顶点与边的关系在图论中，顶点与顶点、顶点与边的关系是通过“邻接(Adjacency)”这个概念来表示的。在无向图G(V,E)中，若(u,v)是图中的一条边，则称u和v互为邻接顶点，边(u,v)依附于u,v，或称(u,v)与u,v相关联。在有向图G(V,E)中,若<u,v>是图中的一条边，则称u邻接到v，v邻接自u，(u,v)与u,v相关联。1.5路径路径是图论中一个很重要的概念。在图G(V,E)中,若从vi出发，沿着一些边经过顶点vp1,vp2,…,vpm，到达顶点vj，则称顶点序列(vi,vp1,vp2,…,vpm,vj)为从顶点vi

到vj的一条路径或通路。路径中边的数量称为路径的长度。

若路径中各顶点vi,vp1,vp2,…,vpm,vj均互相不重复，则称之为简单路径。

若路径中第一个顶点vi与最后一个顶点vj重合，则称此路径为回路。除第一个和最后一个顶点外，没有顶点重复的路径称为简单回路。例如，

在G1中，(0,1,4,3)为0到3的一条路径，且为简单路径,长度为3；在G2中,(2,4,1,5)为2到5的一条路径,长度也为3,而(4,3,2,4)为一简单回路。1.6权值与网络某些图的边具有与之相关的数，称为权值。这些权值可以表示从一个顶点到另一个顶点的距离、时间、代价等。

若一个图的所有边都具有权值，则称之为加权图或网络。根据图中的边是否有向，网络又可以分为有向网和无向网。网络也可以用G(V,E)表示，其中边集E中的每个元素有3个分量：边的两个顶点和权值。例如，下面两图分别为无向网和有向网：

V(G1)={1,2,3,4,5,6}，

V(G2)={1,2,3,4,5,6,7}；

E(G1)={(1,2,28),(1,6,10),(2,3,16),(2,7,14),(3,4,12),(4,5,22),(4,7,18),(5,6,25),(5,7,24)}，

E(G2)={<1,2,12>,<2,4,85>,<3,2,43>,<4,3,65>,<5,1,58>,<5,2,90>,<5,6,19>,<5,7,70>,<6,4,24>,<7,6,50>}。2.图的存储方法图的存储方法有多种，最常用的存储方法是邻接矩阵和关联矩阵。2.1邻接矩阵设无向或有向图G(V,E)，V={v1,v2,…,vn}，E={e1,e2,…,em}。用aij表示vi,vj间的边数，即则称A=(aij)n为图G的邻接矩阵。显然，无向图的邻接矩阵为对称阵。例如，注意：如果图中存在环（连接某个顶点自身的边）和重边（多条边的起点一样，终点也一样）的情形，则无法用邻接矩阵存储。2.2关联矩阵设无向图G(V,E)，V={v1,v2,…,vn}，E={e1,e2,…,em}。用mij表示顶点vi与边ej关联的次数，则称A=(mij)nm为图G的关联矩阵。例如，对有向图G(V,E)，类似地定义2.3网络的邻接矩阵对于网络G(V,E)，邻接矩阵A=(aij)n的定义为其中w(i,j)为连接顶点vi和vj的边的权值。例如，2.4邻接矩阵与关联矩阵的转化邻接矩阵通过顶点与顶点的关系存储图，而关联矩阵则借助顶点与边的关系存储图。相比较而言，邻接矩阵更加常用。邻接矩阵与关联矩阵可以相互转化，具体程序见incToadj.m(无向图)和diincTo

adj.m(有向图)。

例1

已知图G的邻接矩阵为求图G的关联矩阵。结果为

例2

已知图G的关联矩阵为求图G的邻接矩阵。结果为3.作业与上机练习3.1理解图的基本概念及存储方法；3.2写出下列两图的邻接矩阵和关联矩阵：3.3用程序incToadj.m

和diincToadj.m实现上题中邻接矩阵和关联矩阵的相互转化。3.4写出下列网络的邻接矩阵：二、最短路问题

最短路问题是计算机、运筹学、地理信息科学等领域的研究热点之一。在数学建模中，时常出现各类最短路问题。最短路问题是指：若从图中的某一顶点(源点)到达另一顶点(终点)的路径不止一条，如何寻找一条路径，使得沿此路径各边上的权值总和(源点到终点的距离)最小，这条路径称为最短路径。

许多优化问题都等价于在一个图中寻找最短路。例如，管道的铺设、线路的安排、厂址的选取和布局、设备的更新等。最短路问题一般归为两类：一类是求从某个顶点到其他顶点的最短路径，可用Dijkstra算法求解;另一类是求图中每一对顶点间的最短路径，可用Floyd算法求解。

Dijkstra

算法和Floyd算法既适用于无向图，也适用于有向图。1.Dijkstra算法及Matlab程序1.1Dijkstra算法的基本思想设源点为u0，终点为uk。Dijkstra算法的基本思想是:按距离u0由近及远为顺序，依次求得u0到G的各顶点的最短路和距离，直至uk

或G的所有顶点。1.2Dijkstra算法的实现方法为避免重复并保留每一步的计算信息,Dijkstra算法采用标号算法。

(1)设置两个顶点集合T和S；

①S中存放已找到最短路径的顶点，初始时，S中只有u0；

②T中存放当前尚未找到最短路径的顶点；

(2)在T中选取当前长度最短的一条最短路径(u0,…,uk)，从而将uk加入S，并修改u0到T中各顶点的最短路径长度。重复这一步骤，直到所有顶点都加入到S中。

当顶点数较大时,经典Dijkstra算法的运行效率较低。为此，研究人员陆续提出了两个改进算法：DijkstraI和DijkstraII。1.3Dijkstra算法程序及实例

Dijkstra算法及其两个改进算法的程序分别见Dijkf.m，dij1.m和dij2.m。在Dijkf

中，输入为问题的邻接矩阵，输出为3个向量：d,index1,index2。其中di为由源点到第i个顶点的最短距离；index1为顶点标号顺序,index2为标号顶点索引，即第i个元素为源点到第i点的最短路径中第i点前一顶点的序号。在dijk1和dijk2中，输入为问题的邻接矩阵，输出为最短路的距离矩阵。

例3

某公司在6个城市c1,…,c6中有分公司,从ci到cj的直接航班票价见下矩阵(∞表示无直接航班)。请设计从c1到其他城市间票价最低的路线图。

输出结果为

d=[0,35,45,35,25,10]index1=[1,6,5,2,4,3]index2=[1,6,5,6,1,1]

下面以c1到c2为例说明如何使用这一结果。由d易知，c1到c2的最短距离为35。由index2知，c1到c2最短路径中c2之前的一个顶点是c6，c1到c6最短路径中c6之前的一个顶点是c1，从而c1到c2的最短路径是c1->c6->c2。

index2的结果不直观，使用较繁琐。你能改进程序，直接输出最短路径吗？

例4

求下列有向网中u0到其它各顶点的最短路径。

输出结果为

d=[0,20,5,22,28,12]index1=[1,3,6,2,4,5]index2=[1,3,1,6,2,3]从而，u0到其它各顶点的最短距离分别为20,5,22,28,12；最短路径分别为u0->u2->u1,u0->u2，u0->u2->u5->u3，u0->u2->u1->u4，u0->u2->u5。2.Floyd算法及Matlab程序2.1Floyd算法的基本思想

Floyd算法利用了动态规划算法的基本思想，即若dik是顶点ui到uk的最短距离，dkj是顶点uk到uj的最短距离，则dij=dik+dkj是顶点ui到uj的最短距离。2.2Floyd算法的基本步骤设dij是顶点ui到uj的最短距离，wij是顶点ui到uj的权。

(1)输入图G的权矩阵W；

(2)更新dij。对所有i,j，若dij>dik+dkj，则令dij=dik+dkj；

(3)若dij<0，则存在一条含有顶点ui的负回路，停止；或k=n停止；否则转(2)。2.3Floyd算法程序及实例

Floyd算法的程序分别见floyd.m

和n2shorf.m。

floyd中的输入为邻接矩阵，输出为最小、最大标号顶点间的最短路径与最短距离。

n2shorf.m中的输入为邻接矩阵和指定的两个顶点，输出为两个顶点的最短路径与最短距离。你能对程序n2shorf.m进行改进，使其能够输出所有顶点间的最短路径和最短距离吗？

例5

用floyd.m

和n2shorf.m求下图中v0到v7的最短路径和最短距离。

输出结果为

P=[1258]u=11即v0到v7的最短路径为v0->v1->v4->v7，最短距离为11。

例6

用floyd.m

和n2shorf.m求下图中v1到v11的最短路径和最短距离。

输出结果为

P=[1259671011]u=16即v1到v11的最短路径为v1->v2->v5->v9->

v6->v7->v10->v11，最短距离为16。3.作业与上机练习3.1改进Dijkstra

和Floyd算法的程序，使其能够直接输出所有最短路径与最短距离；3.2用Dijkstra算法求v1到其它顶点的最短路径和最短距离。3.3用Floyd算法求v1到v8的最短路径和最短距离(无向边表示双向)。三、最小生成树问题

引例在n个城市间建立通信网络，至少要架设n-1条线路。如何选择这n-1条线路，使得总造价最小？这是一个具有实际意义的问题，可以用图论中的最小生成树解决。本节主要介绍关于树的若干概念、最小生成树问题以及求解方法。本节讨论的图均为无向图。1.树的基本概念不包含圈的连通图称为树。包含图G所有顶点的极小连通子图称为G的生成树。极小是指边的数目极小，即若G有n个顶点，则生成树有n-1条边。例如，下列3个图均为图的生成树：对于赋权无向连通图即无向网，各边权值总和称为生成树的权，权最小的生成树称为最小生成树。2.Kruskal算法和Prim算法求最小生成树的常用方法有Kruskal算法和Prim算法，程序见Krusf.m和Primf.m。例7

用Kruskal算法求下图的最小生成树。

注意:程序Krusf中的d采用的是权值矩阵的另一种表示方法——该矩阵每一列的三个数分别表示此列所对应边的起点、终点和权值，即矩阵的列数即为边数。

运行结果为

T=131144245756—最小生成树的边集合

c=19—最小生成树的权和例8

用Prim算法求下图的最小生成树。结果为T=13453452最小生成树的边集合

c=3124对应边的权3.作业与上机练习3.1分别用Kruskal算法和Prim算法求下图的最小生成树。3.26个城市间的航线距离如下表所示，据此确定最小生成树。四、可行遍性问题哥尼斯堡七桥问题是图论最早研究的问题，中国邮递员问题和旅行商问题也是图论中著名的问题。这些问题本质上都是图论中的最优环游问题。所谓环游或回路是指从图中的一个顶点出发不重复地遍历完所有的边或顶点并回到起始顶点，也称可行遍性问题。最优环游是指赋权图中具有最小权和的环游。中国邮递员问题是最优边环游问题，而旅行商问题则是最优顶点环游问题。本节简要介绍Euler环游和Hamilton环游的概念以及求解两种环游的Fleury算法和改良圈算法。1.Euler环游与Fleury算法经过图G的每条边至少一次的闭迹称为图G的环游。经过每条边仅一次的环游称为图G的Euler环游。包含Euler环游的图称为Euler图。

所谓Euler图就是能不重复行遍所有边再回到出发点的图。哥尼斯堡七桥问题和一笔画问题就是典型的判断图是否为Euler图的问题。

对于赋权图，有时需要寻找具有最小权的环游，称为最优环游。中国邮递员问题就是最典型的最优环游问题。显然,若G是Euler图,则G的任何Euler环游都是最优环游，因为Euler环游是一条通过G的每条边一次的环游。求解Euler环游问题可用Fleury算法,具体程序见Fleuf1.m。

例9

用Fleury算法判断下图是否为Euler图，若是，请找出一条Euler环游。2.Hamilton环游及其求解方法经过图G每个顶点仅一次的环游称为Hamiltion

环游。包含Hamiltion

环游的图称为Hamiltion图。

一名旅行售货员想去访问若干村，最后回到他的出发地。给定各村之间所需的旅行时间，应该怎样计划他的路线，使得这位售货员能对每个村恰好访问一次且总时间最短？这就是著名的旅行售货员问题或货郎担问题(TSP)。旅行商问题其实就是寻找具有最小权的Hamiltion环游，称为最优圈。

TSP现已被证明是NP难问题，没有多项式时间算法。这里给出一种求解TSP问题的近似算法——改良圈算法，具体程序见glf.m。

例10

给定(51,67),(37,84),(41,94),(2,99),(18,54),(4,50),(24,42),(25,38),(13,40),(7,64),(22,60),(25,62),(18,40),(41,26)，试用改良圈算法求通过这14个点的Hamiltion圈。3.作业与上机练习3.1判定下列两图是否为Euler图，若是，则求其Euler环游。3.2给定(5,67),(37,8),(4,94),(200,99),(18,5),(4,50),(4,420),(250,381),(-3,40),(7,-64)，试用改良圈算法求通过这10个点的Hamiltion圈。五、网络流问题网络流问题是图论中一类常见问题。运输问题、指派问题、通信问题等均可转化为网络流问题。许多系统中都包含了流量，如公路系统中的车流，控制系统中的信息流，供水系统中的水流，金融系统中的现金流等。网络流问题包括：网络最大流、流量有界的最大最小流、最小费用最大流、流量有界的最小费用最大流等。本节主要介绍网络流中的一些基本概念、网络最大流、最小费用最大流及其算法。本节讨论的为赋权有向图，权不是表示边的长度，而是表示边的宽度，称之为边的容量。1.基本概念1.1网络与流

本节中所说的网络是指规定了起点和终点的有向赋权图。所谓流可以理解为定义在边上的一个函数。若这个函数满足：

(1)非负性；

(2)不超过边的容量；

(3)除起终点外,其他顶点的流入量等于流出量；则称之为可行流。具有最大流量的可行流称为网络最大流，简称最大流。1.2割设Vs,Vt分别为网络G(V,E)的起终点，则顶点集S和T称为G的割，其中。割(S,T)中的前向弧<u,v>()的容量和称为割的容量。

下面给出图G的两个割，容量分别为21和8。容量最小的割称为最小割。

定理最大流的