1、图论及其应用图论及其应用(Graph Theory with Applications)Applications)闽江学院数学系：魏首柳闽江学院数学系：魏首柳数学建模暑期培训班数学建模暑期培训班一、图的基本概念二、实例分析三、最小生成树问题四、最短路径问题一、图论的基本概念1图论简介 图论是数学的一个分支,以图为研究对象.这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系.用点代表事物,用连接两点的线表示两个事物之间具有特定关系.图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题：十八世纪的哥尼斯堡城中流过
2、一条河（普雷.格尔河），河上有7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。图论简介 KonigsbergKonigsberg 七七桥问题桥问题是否可以是否可以一笔画？一笔画？A B DC DC A B 图论简介 近40年来，随着计算机科学的发展，图论以惊人的速度向前发展，活跃非凡，堪称异军突起。其主要原因有二：（）计算机科学的发展为图论的发展提供了计算工具；（）现代科学技术的发展需要借助图论来描述和解决各类课题中
3、的各种关系，从而推动科学技术不断地攀登新的高峰。图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。2图的定义与记号(3)每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；我们仅讨论无向图和有向图。(4)不与任何结点邻接的顶点称为孤立点，全为孤立点组成的图(无向图和有向图均可)称为空图。(5)在无向图中两顶点间(包括顶点自身)若多于一条边，则称这几条边为重边.在有向图中若同始点和同终点的边多于一条,则称这几条边为重边.图的
4、定义与记号图的定义与记号定义2 子图：给定两个无(有)向图 G=（V,E），G=（V,E）。(1)若 VV 和 EE，则称 G是G的子图；(2)若 VV，EE，且 GG，则称 G是 G 的真子图；(3)若 V=V 和 EE，则称 G是 G 的生成子图(支撑子图)。(4)若子图 G无孤立点且G由E唯一确定，则称G是由边集E导出的子图；(5)若对子图 G=V,E中任二顶点 u,v,(u,v)E(u,v)E，则称 G是由顶点集V导出的子图(易见:V导出的子图G是以V为其顶点集,所有在G中同时关联于V中两点的边为其边集).图的定义与记号图的定义与记号3路径问题与连通问题 定义3(1)设 是赋权图G中从
5、u到v的路径，则称 为路径P的权;(2)在赋权图G中，从顶点u到顶点v的具有最小 权的路 ，称为u到v的最短路。定义2 (1)在无向图G中,若存在一条从顶点u到w的 路 径,则称从u到w可达.约定每个结点到自身 可达;(2)任意两点均有路径的图称为连通图；(3)起点与终点重合的路径称为圈;(4)连通的无圈图称为树。(,)p u v()()()e E Pw Pw e*(,)P u v路径问题与连通问题连通图例不连通图4图的矩阵表示定义 1 关联矩阵（1）对无向图 G，其关联矩阵()ijvMm，其中 ij1,vv0,ijmij若 与 相关联若v 与v 不关联（2）对有向图 G，其关联矩阵()ijv
6、Mm，其中 1,1,0,iijiivmvv jjj若 是e的起点若 是e的终点若 与e 不关联 关联矩阵示例右上图的关联矩阵是右上图的关联矩阵是 右下图的关联矩阵是右下图的关联矩阵是 134521342 110100001010010001101010000110010000011154321 110001011001101000114321图的矩阵表示 定义 2 邻接矩阵（1）对无向图 G，其邻接矩阵()ijv vAa，其中 1,0,ijijijvvavv若 与 相邻若 与 不相邻（2）对有向图 G=（V，E），其邻接矩阵()ijv vAa，其中 1,(,)0,(,)ijijijv vEav
7、 vE若若（3）对有向赋权图 G，其邻接矩阵()ijv vAa，其中 ,(,)0,(,)ijijijijijwv vEwaijv vE若,且为其权若若 邻接矩阵示例右上图的邻接矩阵是右上图的邻接矩阵是 右下图的邻接矩阵是右下图的邻接矩阵是 134521342 01110101011101110101011105432154321 010000001100011043214321图的矩阵表示定义 3 可达矩阵：对有向图 G=（V，E），其可达矩阵()ijv vPp，其中 1,0,ijijijvvpvv若 与 可达若 与 不可达 可达矩阵示例134212341 11112 01113 00104
8、0011右图的可达矩阵是右图的可达矩阵是二、图论模型实例分析 实例一 握手的次数 史密斯先生和他太太邀请四对夫妻参加晚会每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么，史密斯太太和别人握了几次手呢?这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果对此建立一个图模型，问题就变得很简单了。握手的次数分析：从题目我们得到了哪些信息?n史密斯和太太邀请四对夫妻参加晚会房间里共有10 人;n每个人都不会与自己的配偶握手握手的两个人不是配偶;n每个人都不会跟同一
9、个人握手两次两个人间的握手最多是一次;n史密斯先生问每个人和别人握了几次手，他们的答案都不一样除史密斯先生外，每个人和别人握手的次数都不一样;n除史密斯先生外，每个人握手的次数最多是8次，最少为0次;n房间里除了史密斯先生外的9个人，他们与别人握手的次数分别为0，1，2，3，4，5，6，7，8次。握手的次数 要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的9人中哪一个是史密斯太太即可。根据以上信息，建立图模型：握手的次数 由图可知：n8号的配偶是0号；n7号的配偶是1号；n6号的配偶是2号；n5号的配偶是3号；n史密斯太太是4号，所以史密斯太太和别 人握了4次实例二 渡河问题 某人带
10、狗、羊、以及蔬菜渡河，一小船除需人划外，每次只能载一物过河。而人不在场时，狗要吃羊，羊要吃菜，问此人应如何过河？模型构成此问题可化为状态转移问题，用四维向量（人，狗，羊，菜）来表示状态，当一物在此岸时相应分量取1，而在彼岸时则取0。（1）可取状态 人在此岸 人在彼岸 总共有十个可取状态。现在用状态运算来完成状态转移。由于摆一次游戏即可改变现有状态，为此再引入一个四维转移向量，用它来反映摆渡情况用1表示过河，0表示未过河。例如表示人带狗过河。此状态只有四个允许转移向量：现在规定状态向量与转移向量（分量）之间的运算为 渡河问题渡河问题模型求解 通过上面的定义，问题化为由初始状态出发，经过奇数次上述
11、运算转移为状态 的转移过程。可用图表示为 实例三 循环比赛的名次1.1 问题 n支球队循环比赛，每场只计胜负，没有平局.根据比赛结果排出各队名次.图（1）给出了6支球队的比赛结果，即1队战胜2、4、5、6队，而输给了3队；5队战胜3、6队，而输给了1、2、4队等等.循环比赛的名次方法1：寻找按箭头方向通过全部顶点的路径.312456 146325 无法排名 方法2：计算得分：1队胜4场，2，3队各胜3 场，4，5队各胜2场，6队胜1场.2，3 队，4，5队无法排名.32，45 排名132456合理吗？用图论的知识可以解决这个问题.循环比赛的名次1.2 竞赛图及其性质 循环比赛的结果竞赛图：每对
12、顶点之间都有一条边相连的有向图.3个顶点的竞赛图：名次：1,2,3(1,2,3)并列 4个顶点的竞赛图：名次：1,2,3,4 2,(1,3,4)(1,3,4),2 (1,2),(3,4)1,2,3,4?循环比赛的名次循环比赛的名次竞赛图的3种形式：n具有唯一的完全路径，如(1)n双向连通图-任一对顶点存在两条有向路径相互连通，如(4)；n其他，如(2),(3).竞赛图的性质：n必存在完全路径；n若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如（1）.双向连通竞赛图的名次排序 循环比赛的名次循环比赛的名次1.3 模型建立 定义邻接矩阵如下：故（4）的邻接矩阵为 循环比赛的名次
13、记顶点得分向量为 ,则有 1级得分向量 2级得分向量 循环比赛的名次1.4 模型求解 利用著名的Perron-Frobenius定理，素阵A的最大特征根为正单根 ，对应正特征向量s，且有 (归一化后)用s排名.对（4），因 循环比赛的名次 对于本节开始提出的6支球队循环比赛的结果，有：循环比赛的名次所以 ，排出名次为 。课后作业 四名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?三、最小生成树及其应用n定义 无向图G=（V,E）的生成子图T是树,则称
14、T是G的一棵生成树（支撑树）(不唯一）.n任何连通无向图G至少有一棵生成树.n赋权简单连通无向图G=(V,E,W)的子图 H的权定义为 H 的所有边的权和.G中权最小的生成树称为最小生成树(对普通简单连通图不考虑最小生成树).n最小生成树有很强的应用背景,例如:设计联系若干城市的最短线路通信网;设计供应若干居民点的最短自来水管线路等.n最小生成树的求法：破圈法和避圈法求最小生成树的Kruskal算法(避圈法)n算法 将赋权简单连通无向图G的边排序:e1e2em.开始时 k:=1,A:=.步骤步骤 若Aek导出的子图无圈,则 A:=Aek.步骤步骤 若|A|=n-1,算法结束;否则转步骤.例例
15、对左边无向图对左边无向图用用KruskalKruskal算法求算法求得右边的最小生成树得右边的最小生成树.1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 1 2 3 4 5 6 7=n-1=n-11234567891011121235689求最小生成树的破圈法n此法1975年由中国数学家管梅谷教授首先提出,具体算法如下:将赋权简单连通无向图G=V,E的边排序:e1e2em.开始时 A:=E.步骤 若A无圈,则A是最小生成树,算法结束,否则转步骤.步骤 在A中任取的一条回路C中取有最大权的边e,置A:=A-e后
16、转步骤.n破圈法的正确性基于下列事实:G的任何一条简单回路C中权最大的边f一定不属于任何最小生成树T.(C必有一边e不属于T,若f属于T,则以e代f所得的生成树T的权W(T)=W(T)+W(e)-W(f)W(T),产生矛盾.)最小生成树实例:有线电视网最优布线问题 单位：100米1.问题重述:卫星加密电视的开播,受到大家的欢迎,要想收看加密电视必须建立一套有线电视网我们考虑这样一个具体问题：设某市六个个区之间的相互距离如下表所示，试确定该表数据形成的网络中，如何布线才能使布线最省？1 2 3 4 5 6 1 0 13 51 77 68 502 13 0 60 70 67 593 51 60 0
17、 57 3 624 77 70 57 0 20 555 68 67 36 20 0 346 50 59 2 55 34 0最小生成树实例:有线电视网最优布线问题 .问题求解:最优布线问题，就是要求任何两地都有链相连，而使总线路最短，这个问题在图论中也称为最小树问题作下图，其中顶点v1，v，v，v，v，v 分别表示两区之间的距离V1V6V3V5V4V260702013675977575568512343650最小生成树实例:有线电视网最优布线问题 对于上图，我们要找使布线最省的网络模型图论中的破圈法可以解决这个问题，具体过程如下：在圈v1vvv1中，去掉最长边vv60，同样去掉圈v1vvv1，v
18、vvv，vvvv，v3 v5vv3，v4v5 v6 v4，v1v3v4v1，v1v6v2v1，v2v5v6v2中最长的边v1v51，v2v470，v3v457，v3v536,v4v655，v1v477，v1v568，v2v659，v2v567，最后构成的图（如下）就是最省的布线图132503420v2v3v1v6v4v6四、最短路径问题及其应用 最短路问题就是从给定的网络图中找出任意两点间距离最短的一条路，其中距离只是权数的代称（在实际网络中，权数可指时间、费用等）。如选址、管道铺设时的选线、设备更新、投资等都可以归给为求最短路的问题。最短路问题有一个重要而明显的性质（算法思想）：最短路是一条
19、路径，且最短路的任一段也是最短路。求最短路的方法：(1)求从一点到其余各点间的Dijkstra算法;(2)求任意两点间最短距离的矩阵算法(Floyd算法)。设G为赋权有向图或无向图，G边上的权均非负。Dijkstra(标号法）的算法：不妨用表示图中两相邻点i和j的距离；若点I和j不相邻，则可令，显然；用表示从点s到i点的最短距离。现要求从点到某一点t的最短路。Dijkstra算法步骤如下：（）从点s出发，因，将此值标在s旁，表示此点已标号；（）从s点出发，找出与s点相邻的点中距离最小的一个，设为r，将的值标在r旁，表示此点已标；（）从已标号的点出发，找出与这些点相邻的所有未标号点p。若有，则对
20、p点标号；（）重复第三步，一直到t点得到标号为止。矩阵算法步骤（略）ijdijd 0iid siL0ssL srsssrLLdmin;spssspsrrpLLdLd 例 求图中顶点v0与v5的最短路径.解:可以将计算过程用一张表表示出来(见下页表)算法示例由上表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样从v5往前追踪,得v0到v5的最短路径为：=v0v1v2v4v3v5.W()=9.Dijkstra算法的标号法举例21073645210736452210736452107364510 2 95225599990000最短路径问题实例：医院选址问题
21、1.问题重述：新建居民小区的医院，对该区每一户居民都很重要。如下图是一个新建居民区的示意图，医院建在哪里为好呢？V2V1V3V5V10V7V6V4V9V893218279564813165 最短路径问题实例：医院选址问题在上图中，v1，v，v10表示各居民点，边表示两居民点之间的道路，边上的数值表示两居民点之间的距离（也就是该边的权）.现在需要我们考虑的问题是在这10个居民点中，何处作为新建医院的理想地址，以使所建医院到最远的居民点距离尽可能近（即最远点的病人到医院看病时走的路尽可能短）。2.问题求解：显然可以看出，上图是一个连通无向图，记为，.任取vi V(i=1,2,10)，考察vi与中其
22、他顶点间的最短路（也称为距离）：（vi，v），（vi，v2），（vi，v），把这10个距离中最大的数称为顶 vi的最大服务距离，记为L(vi).求出上图中各点间的距离，如下表所示，这样就可以把每个顶点vi对应的最大服务距离L(vi)求出来.最短路径问题实例：医院选址问题最短路径问题实例：医院选址问题1 2 3 4 5 6 7 8 9 1010 5 3 6 5 10 10 9 12 1325 0 2 3 4 9 6 8 8 933 2 0 3 2 7 7 6 9 1046 3 3 0 5 7 5 6 7 855 4 2 5 0 5 5 4 7 8610 9 7 7 5 0 2 1 4 5710
23、6 7 5 5 2 0 1 2 389 8 6 6 4 1 1 0 3 4912 8 9 7 7 4 2 3 0 51013 9 10 8 8 5 3 4 5 0最短路径问题实例：医院选址问题 注：上表中的，分别代表v1，v，v，v，v，v，v，v，v，v v1到各顶点的距离就是上表中的第一行各数，它们中最大的是13，所以L(v1)=13，其它各点的最大服务距离分别为:L(v2)=9，L(v3)=10，L(v4)=8，L(v5)=8，L(v6)=10，L(v7)=10，L(v8)=9，L(v9)=12，L(v10)=13。由于，所以把医院建在v4或v5为较好的选择，进一步调查，如果居民点v的居民比v5多，那么把医院建在v最好.110min()8iiL v
