数学建模5图论

《数学建模5图论》由会员分享，可在线阅读，更多相关《数学建模5图论（67页珍藏版）》请在装配图网上搜索。

1、2021/6/31数学建模数学建模-图论2021/6/32前言 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。传统的物理、化学、生命科学也都越来越广泛地使用了图论模型方法。2021/6/33从七桥问题说起 -关于图模型 在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图）。问题的提出问题的提出 哥

2、尼斯堡七桥问题 七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实故事。ABCD2021/6/34 为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现。ABCD 1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。2021/6/35 问题分析与模型假设：问题分析与模型假设：2.四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的本质无关

3、，因而可视四块陆地为四个点 A、B、C、D。1.问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形状、长短、曲直等均无关，而只要桥存在，因此不妨将其视为一条弧线ABCDABDC2021/6/36 对四个陆地 A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为 边。这样一来，能否从一地出发走遍七座桥一次且仅一次再回到出发点就变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。这就是众所周知的这个图能否“一笔画出”的问题。ABCDABDC2021/6/37 能否从这个图

4、上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。“一笔画出一笔画出”能否从这个图上任一顶点出发，经过每个顶点一次且仅一次而回到出发顶点。旅行商问题旅行商问题 能否从这个图选择尽量少的点，使得所有的其余点都和该点集有路径连接。覆盖问题覆盖问题-系统监控模型系统监控模型 能否将图中点集分类，使得每一类点集都没有路径连接，最少需要分几类。支配集支配集-仓库分区仓库分区2021/6/38 将该图中所有顶点用不同颜色表示，最少需要几种颜色。“点着色 将该图中所有边用不同颜色表示，最少需要几种颜色。边着色边着色关键路径关键路径最大流、最小流最大流、最小流2021/6/39问题问题2(2(哈密顿环球旅

5、行哈密顿环球旅行问题问题):):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）2021/6/310问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.2021/6/311问题问题4(4(关键路径问题关键路径问题):):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够

6、预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？2021/6/312图的基本概念图的基本概念最短路问题及其算法最短路问题及其算法最小生成树问题最小生成树问题图的矩阵表示图的矩阵表示2021/6/313 132022年年9月月5日日 一、图的基本概念一、图的基本概念2021/6/314 142022年年9月月5日日 一、图的基本概念一、图的基本概念图图1 1图图2 22021/6/315 152022年年9月月5日日 一、图的基本概念一、图的基本概念 一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E

7、)的图解.其中 V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4.2021/6/316 162022年年9月月5日日 一、图的基本概念一、图的基本概念2021/6/317 172022年年9月月5日日 一、图的基本概念一、图的基本概念次数为奇数顶点称为次数为奇数顶点称为奇点奇点，否则称为否则称为偶点偶点。2021/6/318 182022年年9月月5日日 一、图的基本概念一、图的基本概念常用常用d d(v v)表示图表示图G G 中与顶点中与顶点v v关联的边的数目关联的边的数目,d d(v v)称为顶点称为顶点v v的度数的度数.与顶点与顶点v v出

8、关联的边的数目称为出关联的边的数目称为出度出度，记作，记作d d +(v v)，与顶点与顶点v v入关联的边的数目称为入关联的边的数目称为入度入度，记作，记作d d -(v v)。用用N N(v v)表示图表示图G G 中所有与顶点中所有与顶点v v相邻的顶点的集合相邻的顶点的集合.任意两顶点都相邻的简单图称为任意两顶点都相邻的简单图称为完全图完全图.有有n n个顶点的完全图记为个顶点的完全图记为K Kn n。2021/6/319 192022年年9月月5日日 一、图的基本概念一、图的基本概念几个基本定理：几个基本定理：.21EvdEVGVv，有，、对图数个。、度为奇数的顶点有偶2 .3Evd

9、vdEVGVvVv则是有向图，、设2021/6/320 若将图若将图G G的每一条边的每一条边e e都对应一个实数都对应一个实数F F(e e),则称则称F F(e e)为该边的为该边的权权,并称图并称图G G为为赋权图赋权图,记为记为G G=(=(V V,E E,F F ).设设G G=(=(V V,E E)是一个图是一个图,v v0 0,v v1 1,v vk kV V,且且“11i ik k,v vi i1 1 v vi iE E,则称则称v v0 0 v v1 1 v vk k是是G G的一条的一条通路通路.如果通路中没有相同的顶点如果通路中没有相同的顶点,则称此通路为则称此通路为路径

10、路径,简称简称路路.始点和终点相同的路称为始点和终点相同的路称为圈圈或或回路回路.一、图的基本概念一、图的基本概念 2021/6/321 顶点顶点u u与与v v称为称为连通连通的，如果存在的，如果存在u u到到v v通路，任二顶通路，任二顶点都连通的图称为点都连通的图称为连通图连通图，否则，称为，否则，称为非连通图非连通图。极大。极大连通子图称为连通子图称为连通分图连通分图。连通而无圈的图称为连通而无圈的图称为树树,常用常用T T 表示树表示树.树中最长路的边数称为树的树中最长路的边数称为树的高，高，度数为度数为1 1的顶点的顶点称为称为树叶树叶。其余的顶点称为。其余的顶点称为分枝点分枝点。

11、树的边称为。树的边称为树树枝枝。设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。一、图的基本概念一、图的基本概念 2021/6/322 一、图的基本概念一、图的基本概念(应用应用)用图论思想求解以下各题用图论思想求解以下各题例例1、一摆渡人欲将一只狼，一头羊，一篮菜从、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。2021/6/323 一、图的基本概念

12、一、图的基本概念(应用应用)解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取状态，（在西岸则分量取1，否则取，否则取0.）共共24=16种状态，种状态，由题设，状态（由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不是不允许的，允许的，从而对应状态（从而对应状态（1,0,0,1），），(1,1,0,0),(1,0,0,0)也是也是不允许的，不允许的，2021/6/324 一、图的基本概念一、图的基本概念(应用应用)人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0

13、,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。2021/6/325 一、图的基本概念一、图的基本概念(应用应用)例例2、考虑中国象棋的如下问题：、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？）马有多少种跳法？（3）马跳出后又跳回起点，证

14、明马跳了偶数步。）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？的跳遍每一点，最后跳回起点？2021/6/326 一、图的基本概念一、图的基本概念(应用应用)例例3、证明：在任意、证明：在任意6人的集会上，总有人的集会上，总有3人互相认人互相认识，或总有识，或总有3人互相不认识。人互相不认识。解：以顶点表示人，以边表示认识，得解：以顶点表示人，以边表示认识，得6个顶点个顶点的简单图的简单图G。问题：问题：3人互相认识即人互相认识即G包含包含K3为子图，为子图，3人互相不认识即人互相不认识即G

15、包含（包含（3,0）图为子图。）图为子图。2021/6/327 一、图的基本概念一、图的基本概念(应用应用)为子图。包含点不相邻，则点至少、这图为子图。包含点两两相邻，则、这。这又包含两种情况：点不相邻个顶即至少与另外个顶点相邻至多与另外）（为子图。包含点相邻，则点至少、这图为子图。包含点互不相邻，则、这两种情况：个顶点相邻，这又包含至少与另外则有两种情况：任取0,3232 31 )3(22232 0,331 3 1,33GKGvKGGvGVv2021/6/328282022年年9月月5日日一、图的基本概念一、图的基本概念(应用应用)（设备更新问题）某企业每年年初（设备更新问题）某企业每年年初

16、,都要作出决定都要作出决定,如果继续使用旧设备如果继续使用旧设备,要付维修费；若购买一台新设要付维修费；若购买一台新设备备,要付购买费要付购买费.试制定一个试制定一个5 5年更新计划年更新计划,使总支出使总支出最少最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别为使用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18.2021/6/329292022年年9月月5日日ijkkijicbvvF1)(求求v v1 1到到v v6 6的最短路问题的最短路问题.一、

17、图的基本概念一、图的基本概念(应用应用)4 11411()11 568kkF vvbc 2021/6/330302022年年9月月5日日从上图中容易得到从上图中容易得到v v1 1到到v v6 6只有两条路只有两条路：v v1 1v v3 3v v6 6和和v v1 1v v4 4v v6 6.而这两条路都是而这两条路都是v v1 1到到v v6 6的最短路的最短路.一、图的基本概念一、图的基本概念(应用应用)2021/6/331邻接矩阵（结点与结点的关系）邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）路径矩阵（任意两结点之

18、间是否有路径）可达性矩阵可达性矩阵直达矩阵直达矩阵 等等等等二、图的矩阵表示二、图的矩阵表示 2021/6/3321 1 有向图的邻接矩阵有向图的邻接矩阵 A=(aij)nn（n为结点数）EvvEvvajijiij,0,1 例例1 1：写出右图的邻接矩阵：写出右图的邻接矩阵：0101100101001010A解：二、图的矩阵表示二、图的矩阵表示 2021/6/3332 2 有向图的权矩阵有向图的权矩阵A=(aij)nn（n为结点数）EvvjiEvvvvFajijijiij ,0 ,例2：写出右图的权矩阵：05420370860A解：二、图的矩阵表示二、图的矩阵表示 2021/6/3343 有向

19、图的有向图的关联矩阵关联矩阵A A=(aij)nm（n为结点数m为边数）不关联与若的终点是若的始点是若iiiiiiijeveveva,0,1,1有向图：有向图：无向图：无向图：不关联与若关联与若jijiijvvvva,0 ,1 二、图的矩阵表示二、图的矩阵表示 2021/6/335例例3 3：分别写出右边两图的关联矩阵：分别写出右边两图的关联矩阵解：分别为：1101100011011000000111011001A 二、图的矩阵表示二、图的矩阵表示eabcd1e2e3e4e5e0001101001111000011010000A 2021/6/336 二、图的矩阵表示二、图的矩阵表示4 4 应

20、用实例应用实例 某航空公司在A,B,C,D四城市之间开辟了若干航线,如图所示表示了四城市间的航班图,如果从A到B有航班,则用带箭头的线连接 A 与B.问题:如何直观给出各个城市之间的航班情况 问题:如果没有直接航班到达,需要转机,有几种转机方案问题:如果城市不止4个,有n个城市,能否快速给出直接路径 以及需要转机方案.问题:过年回家火车路线如何设置，北京公交地铁倒车如何如何设置 百度地图2021/6/337 二、图的矩阵表示二、图的矩阵表示 00101001010101100010100101010110MM0010100101010110MABCD.20111 1110 2101 010数值

21、 表示两地之间航线的数目，1表示只有一条路径，2代表有两条路径2021/6/338 若将图若将图G G 的每一条边的每一条边e e都对应一个实数都对应一个实数F F(e e),则称则称F F(e e)为该边的为该边的权权,并称图并称图G G为为赋权图赋权图,记为记为G G=(=(V V,E E,F F ).设设G G=(=(V V,E E)是一个图是一个图,v v0 0,v v1 1,v vk kV V,且且“11i ik k,v vi i1 1 v vi iE E,则称则称v v0 0 v v1 1 v vk k是是G G的一条的一条通路通路.如果通路中没有相同的顶点如果通路中没有相同的顶点

22、,则称此通路为则称此通路为路径路径,简称简称路路.对于赋权图，对于赋权图，路的长度（即路的权）路的长度（即路的权）通常指路上所有边通常指路上所有边的权之和。的权之和。最短路问题最短路问题：求赋权图上指定点之间的权最小的路。：求赋权图上指定点之间的权最小的路。三、最短路问题及其算法三、最短路问题及其算法 2021/6/339重要性质：重要性质：若若v v0 0 v v1 1 v vm m 是是G G 中从中从v v0 0到到v vm m的最短路的最短路,则则对对11k km m,v v0 0v v1 1 v vk k 必为必为G G 中从中从v v0 0到到v vk k的的最短路最短路.即：最短

23、路是一条路，且最短路的任一段即：最短路是一条路，且最短路的任一段也是最短路。也是最短路。三、最短路问题及其算法三、最短路问题及其算法 2021/6/340 设有给定连接若干城市的公路网，寻求从指定城设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。市到各城市的最短路线。2、应用实例：最短路问题、应用实例：最短路问题 问题的数学模型问题的数学模型:三、最短路问题及其算法三、最短路问题及其算法402022年年9月月5日日 2021/6/341412022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 2021/6/342422022年年9月月5日日 三、最短路问题及其

24、算法三、最短路问题及其算法 2021/6/343432022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 例例 求下图从顶点求下图从顶点 u u1 1 到其他顶点的最短路到其他顶点的最短路03064093021509701608120W邻接矩阵为邻接矩阵为2021/6/344442022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u

25、6u 2u 5u 4u 5u2021/6/345452022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 例例 matlabmatlab程序程序 road1.mroad1.m运行结果如下：运行结果如下：l=0 2 1 7 3 6 9 12z=1 1 1 6 2 5 4 52021/6/346462022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 u1u2u3u4u5u6u7u82021/6/3472022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 作业：对下面的有向图求顶点作业：对下面的有向图求顶点v0到其余顶点的最短路。到其余顶点的最

26、短路。0v2v1v3v4v5v14456425372021/6/3482022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；标号算法；Dijkstra标号算法只适用于标号算法只适用于全部权为非负情况全部权为非负情况。求非负赋权图上任意两点间的最短路，一般用求非负赋权图上任意两点间的最短路，一般用Floyd算法算法.Floyd算法可以适用于有负权的情况，还能判断是算法可以适用于有负权的情况，还能判断是否有负回路。否有负回路。这两种算法均适用于有向赋权图这两种算法均

27、适用于有向赋权图.2021/6/3492022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 Floyd算法：算法：求任意两顶点的最短路求任意两顶点的最短路 设设A=(aij)nn为赋权图为赋权图G=(V,E,F)的权矩阵的权矩阵,dij表表示从示从vi到到vj点的距离点的距离,rij表示从表示从vi到到vj点的最短路中一个点的最短路中一个点的编号点的编号.赋初值赋初值.对所有对所有i,j,dij=aij,rij=j.k=1.转向转向.更新更新dij,rij.对所有对所有i,j,若若dik+dk jdij,则令则令dij=dik+dkj,rij=k,转向转向;终止判断终止判断.

28、若若k=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.2021/6/3502022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 32v1v3v4v5v29724例例 求如下加权图的任一两点间的最短距离和路径求如下加权图的任一两点间的最短距离和路径road2.m floyd.m road2.m floyd.m 2021/6/3512022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 5333334331543243332344441,0646960243420256420793570RD32v1v3v4v5v297245

29、v1v3v4v例例 matlabmatlab程序程序 road2.m floyd.m road2.m floyd.m 2021/6/3522022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 作业作业 求下列加权图中任意两点间的最短距离和路径求下列加权图中任意两点间的最短距离和路径1v3v2v4v5v685233742021/6/353532022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 选址问题选址问题:在在 n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问设问设在哪个点在哪个点,可使最大服务距离最小可使最大服务距离最小?若设两个银行若

30、设两个银行,问设问设在哪两个点在哪两个点?模型假设模型假设 设各设各个个居民点都有条件设置银行居民点都有条件设置银行,并有并有路相连路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.2021/6/354542022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 求k,使.min1inikdd 即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小.设置一个银行,银行设在 vi 点的最大服务距离为.,.,2,1,max1niddijnji2

31、021/6/355552022年年9月月5日日 三、最短路问题及其算法三、最短路问题及其算法 设置两个银行,假设银行设在vs,vt 点使最大服务 距离最小.记.,minmax),(1jkiknkddjid则s,t 满足：).,(min),(1jidtsdnji进一步进一步,若设置多个银行呢？若设置多个银行呢？2021/6/356562022年年9月月5日日 作业：作业：1 1、一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要 将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监 视的情况下留在一起。问摆渡人应怎样把它们运过河去？2、北

32、京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表，请应用最短路方法，给出北京到其他城市的最短路，并通过图的形式标出。2021/6/357572022年年9月月5日日 例系统监控模型:居民区如图所示,ei为街道,vi为交叉路口,计划在交叉路口安置消防设施,只有与路口相邻的街道才能使用它们.为使街道必要时都有消防设施使用,在那些路口安置设施最节约?覆盖集：KV(G),对任意eE，则e至少一顶属于K，则K为G一个 覆盖集；若K是G的覆盖集，对与任意vK,K-V不是覆盖集。则K是 G的极小覆盖集。含顶最少覆盖集为最小覆盖集。最小覆盖集中所含顶数为图

33、G的覆盖数。2021/6/358582022年年9月月5日日 e1e4e3e2e5e6e7v1v2v3v4v5问题归结为求最小覆盖(1)建立关联矩阵e1 e2 e3 e4 e5 e6 e7v1 1 0 0 1 0 0 0v2 1 1 0 0 1 0 0v3 0 1 1 0 0 1 0v4 0 0 1 1 0 0 1v5 0 0 0 0 1 1 12021/6/359592022年年9月月5日日 e1 e2 e3 e4 e5 e6 e7v1 1 0 0 1 0 0 0v2 1 1 0 0 1 0 0v3 0 1 1 0 0 1 0v4 0 0 1 1 0 0 1v5 0 0 0 0 1 1 1e

34、1 e4 e5 e7v1 1 1 0 0v2 1 0 1 0v4 0 1 0 1v5 0 0 1 1 (3)划去v对应的行及1所在列 e4 e7v1 1 0v4 1 1v5 0 1 (2)寻含1最多的顶v归于K(例v3K)(4).在剩余矩阵内重复以上过程直至矩阵空K=v2 v3 v42021/6/360 支配集：DV(G),若图G中任意顶vD，则v必与D内一顶相邻，则D为G的一个支配集。若D是G的覆盖集，若D的任意子集不是支配集。则D是G的极小支配集。含顶最少的支配集为最小支配集。最小支配集中所含顶数为图G的支配数。例2:如图6个城镇v1 v2v6建立通信系统,从中选几座城镇建中心台站,要求它

35、们与各城镇相邻,为减少造价使中心台站数目最少.请提供建立方案.若在造价最低的条件下,建两套通信中心,以备出故障时启用另一套请提供建立方案.v6v2v1v3v4v52021/6/361归为求最小支配(1)写出邻接矩阵A,将主对角线元素全改为1.即A+E.v1 v2 v3 v4 v5 v6v1 1 1 1 1 0 0v4 1 1 1 1 1 1v2 1 1 0 1 0 0v3 1 0 1 1 0 0v5 0 0 0 1 1 1v6 0 0 0 1 1 1(3)划去A+E中v对应的行及1所在列(2)寻含1最多的顶v归于D (例v4D)(4).在剩余矩阵内重复以上过程直至矩阵空 若建两套通信中心,可在

36、A+E划去v4对应的行,在剩余矩阵(A+E)2中重复以上过程 v1 v2 v3 v4 v5 v6v1 1 1 1 1 0 0v2 1 1 0 1 0 0v3 1 0 1 1 0 0v5 0 0 0 1 1 1v6 0 0 0 1 1 12021/6/362v5 v6v2 0 0v3 0 0v5 1 1v6 1 1D=v1 v5 独立集：IV(G),I中任意两顶不相邻，则I为G的一个独立集。若I是G的独立集，对与任意uV(G),Iu不是独立集。则I是G的极大独立集。含顶最多的独立集为最大独立集。最大独立集中所含顶数为图G的独立数。定理：K为极小覆盖VK为极大独立集。极大独立集必为极小支配集,反之

37、不成立.2021/6/363 例3.公司生产a,b,c,d,e,f,g 7种化学品,其中(a,b)(a,d)(b,c)(b,e)(b,g)(c,d)(c,e)(c,f)(d,e)(d,g)(e,f)(f,g)不能放在一起,公司必须把仓库分成若干个区,以便把不相容的制品分开,问至少分几个区,怎样存放才能保证安全.以顶va vb vg表示7种化学制品,在不相容制品间连边得图Gvfvavbvcvdvgve归为求最大独立集(也可用顶点着色)先求最小覆盖K1,则S1=V-K1为一个最大独立集.再求最小覆盖V-S1,最大独立集S2.再求最小覆盖V-S1-S2,最大独立集S3.2021/6/364问题归结为

38、求最小覆盖(1)建立关联矩阵 (2)寻含1最多的顶v归于K(例vbK)vfvavbvc vdvgveeab ead ebc ecd ebg ebe ece eef efg edg ecf va 1 1 0 0 0 0 0 0 0 0 0vb 1 0 1 0 1 1 0 0 0 0 0vc 0 0 1 1 0 0 1 0 0 0 1vd 0 1 0 1 0 0 0 0 0 1 0ve 0 0 0 0 0 1 1 1 0 0 0vf 0 0 0 0 0 0 0 1 1 0 1vg 0 0 0 0 1 0 0 0 1 1 01,bcdfKV V V V1,V,aegGKVV2021/6/365寻含1

39、最多的顶v归于K2(eab ead ebc ecd ebg ebe ece eef efg edg ecf va 1 1 0 0 0 0 0 0 0 0 0vb 1 0 1 0 1 1 0 0 0 0 0vc 0 0 1 1 0 0 1 0 0 0 1vd 0 1 0 1 0 0 0 0 0 1 0ve 0 0 0 0 0 1 1 1 0 0 0vf 0 0 0 0 0 0 0 1 1 0 1vg 0 0 0 0 1 0 0 0 1 1 01,bcdfKV V V V1,aegGKV e V 2cKV12,bdfKKV e V ,aegbdfcV V VV V VV2021/6/366vfvavbvc vdvgve ,aegbdfcV e VV e VV 用于科普，若有不用于科普，若有不当之处，请指正，感当之处，请指正，感谢您的下载。谢您的下载。