数学建模之图论模型讲解

图论模型数学系孙艳蕊[e-mail]主要内容图模型最短路问题最小生成树问题旅行售货员问题最大流问题图论的基本概念匹配问题一、图模型例1.哥尼斯堡七桥问题(18世纪，1736年)(1)问题能否从一块陆地出发,走遍每座桥一次且仅一次然后回到出发地?ABCD普瑞格尔河(2)问题分析与模型假设问题的本质是能否从一地无重复地一次走遍七桥,与所走过的桥的大小、形状、长短、曲直等均无关，因此不妨将其视为一条弧线；四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的无关，因而可视四块陆地为四个点A、B、C、D。对四个陆地A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为边。ABCD问题变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。--Euler-回路(圈)问题。ABCD例2药品存储问题有8种化学药品A、B、C、D、P、R、S和T要放进贮藏室保管,出于安全原因,下列各组药品不能贮在同一室内:A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D，试为这8种药品设计一个使用房间数最少的贮藏方案。A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D.ARDSBTCP至少需用3个房间：A,S,B/D,T,R/C,P每种药品作为一个顶点，不能放在一起的连边。相邻顶点用不同颜色着色。这一问题就是图论中的顶点着色问题。例3最短路问题（SPP－shortestpathproblem）一名司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，有多种行车路线，这名司机应选择哪条线路呢？假设车的运行速度是恒定的。这一问题相当于找到一条从甲地到乙地的最短路。6v6v5v1v3v236511333v4甲地乙地例4中国邮递员问题（chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。若将投递区的街道用边表示，街道的长度为边的权，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的Euler回路.例5旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城镇推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城镇恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是旅行商问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题-Hamilton圈问题。例6人员分派问题某公司准备分派n个工人X1,X2,…,Xn做n件工作Y1,Y2,…,Yn，已知这些工人中每个人都能胜任一件或几件工作。试问能否把所有的工人都分派做一件他所胜任的工作？构造一个具有二分类(X,Y)的偶图G，这里X={x1,x2,…,xn}，Y={y1,y2,…,yn}，且xi与yj相连当且仅当工人Xi胜任工作Yj.于是问题转化为G是否存在完美匹配的问题。y1x1y2x2x5y5x3x4y4y3例7最小费用最大流一批货物要从工厂运至车站，可以有多条线路进行选择，在不同的线路上每吨货物的运费不同，且每条线路的运输能力有限。怎样运输才能使费用最少?用结点s代表工厂，t代表车站，线路为边，线路的交点为网络的结点，每条边都有两个权：容量c和单位费用a，于是构成网络流图N，问题变成求N的最小费用流。过河问题：摆渡人Ferryman,狼wolf,羊sheep,卷心菜cabbage过河问题.如何摆渡使得它们不能互相伤害.考试安排问题：学校期末考试安排n门课的考试时间时，不能把同一位学生选修的两门课安排在同一时间考试，问学校考试最少要进行多长时间？信道分配问题：发射台所用频率从小到大编号为1,2,…称为信道。用同一信道的两个台站相距得少于一个常数d，问各台至少需同时使用几个不同的信道？指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？…………二、图论的基本概念（略）1.图的概念V(G)中的元素称为图G的顶点；E(G)是V(G)中的无序中的元素称为边.),(jivv|V(G)|：图的顶点数；|E(G)|：图的边的数。表示边jivv).,(jivv},,,{)(21nvvvGV是非空有限集，称为顶点集，或有序的元素对).,(EVG))(),((GEGVG表示图，简记用组成的集合，称为边集,E(G)一个图G是指一个二元组(V(G),E(G))，其中平凡图：只有一个顶点的图。图：无向图，有向图和混合图。ABCDe1e5e7e6e3e4e2V={A,B,C,D}，E={e1,e2,e3,e4,e5,e6,e7}v3v2v1v0e1e2e3e4e5e6V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5,e6}无向图有向图孤立结点:不与任何边关联的顶点.零图:仅由一些孤立结点构成的图.常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．cabd常用术语6)任意两顶点都相邻的简单图,称为完全图.记为Kn.，K5K3YXGV)(YX，则称Ｇ为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻,称为完全二部图或完全偶图，记为(m=|X|,n=|Y|)．nmK,1x2x3x1y2y3y4y1x2x3x1y2y3y4y7)若且两个点集X与Y的内部任意两顶点不相邻，4,3K2．赋权图与子图定义若图的每一条边e都赋以))(),((GEGVG一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图.定义设和是两个图.),(EVG),(EVG1)若,称是的一个子图．EEVV,GG2)若，，则称是的生成子图.VVEEGG3)若，且，以为顶点集，以两端点VVVV均在中的边的全体为边集的图的子图，称VG为的由导出的子图，记为.GV][VG4)若，且，以为边集，以的端点EEEEE集为顶点集的图的子图，称为的由导出的GGE边导出的子图，记为.][EG}],,[{321vvvG}],,,[{6543eeeeG3)若，且，以为顶点集，以两端点VVVV均在中的边的全体为边集的图的子图，称VG4)若，且，以为边集，以的端点EEEEE集为顶点集的图的子图，称为的由导出的GGE边导出的子图，记为.][EGGV][VG为的由导出的子图，记为.3图的矩阵表示(1)邻接矩阵:1)对无向图，其邻接矩阵，其中：G()ijnnAa.,0,,1不相邻与若相邻与若jijiijvvvva12345123450110010100110110010000100vvvvvvvAvvv(以下均假设图为简单图)2)对有向图,其邻接矩阵,其中：()ijnnAa),(EVG.),(,0,),(,1EvvEvvajijiij若若010000100000111043214321uuuuAuuuu(2)关联矩阵1)对无向图，其关联矩阵,),(EVGmnijmM)(其中：.,0,,1不关联与若相关联与若jijiijevevm10000010001111000101000115432154321vvvvvMeeeee2)对有向图，其关联矩阵,),(EVGmnijmM)(.,0,,1,,1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：11000101100001101101432154321uuuuMeeeee4.顶点的度定义在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度，记为d(v).在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的度．定理.2)(Vvvd推论任何图中奇点的个数为偶数．5.路和连通定义无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替kkveevevW2110地为顶点和边，使得对，的端点是和,ki1ie1iviv称W是从到的一条途径，或一条途径.整0vkv),(0kvv数k称为W的长.顶点和分别称为的起点和终点,0vkv而称为W的内部顶点.121,,,kvvv若途径W的边互不相同但顶点可重复，则称W为迹或简单链.若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路0vkv),(0kvv记为).,(0kvvP起点与终点重合的途径称为闭途径.起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck.若在图G中存在(u,v)路，则称顶点u和v在图G中连通.图G中任意两点皆连通的图称为连通图．例在右图中：途径或链：迹或简单链：路或路径：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg三、最短路问题及算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.•最短路问题的两种方法：Dijkstra和Floyd算法.1)求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.在赋权图G中，从顶点u到顶点v的具有最小权的路称为路P(u,v)的权．若P(u,v)是赋权图G中从u到v的路,称)()()(PEeewPwP*(u,v)，称为u到v的最短路．把赋权图中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作d(u,v).在赋权图中找出指定两点之间的最短路的问题称之为最短路问题。赋权图中求给定点到各顶点的最短路的算法(Dijkstra算法，1959年）令图G=V,E,W,集合SiV,Si=V-Si,令|V|=nSi={u|从u0到u的最短路已求出}Si={u|从u0到u的最短路未求出}基本思想:若使(u0,u1,u2,…,un-1,un)最短,就要使(u0,u1,u2,…,un-1)最短,即保证从u0到以后各点的路都是最短的.Dijkstra算法:(求从u0到各点u的最短路长)第一步.置初值:d(u0,u0)=0d(u0,v)=∞(其中v≠u0)i=0S0={u0}S0=V-S0,第二步.若i=n-1则停.否则转第三步第三步.对每个u∈Si计算d(u0,u)=min{d(u0,u),d(u0,ui)+c(ui,u)}ui∈Siu∈Si计算min{d(u0,u)}并用ui+1记下达到该最小值的那个结点u',置Si+1=Si∪{ui+1},i=i+1Si=V-Si,转第二步.例.求右图中从v1到v6的最短路。d(u0,v2)=3,路u0v2d(u0,v4)=4,路u0v2v4d(u0,v5)=5,路u0v2v4v5d(u0,v3)=7,