运筹学基础及应用第五版-胡运权.ppt
《运筹学基础及应用第五版-胡运权.ppt》由会员分享,可在线阅读,更多相关《运筹学基础及应用第五版-胡运权.ppt(70页珍藏版)》请在咨信网上搜索。
1、第6章 图与网络分析Graph and Network Analysis 图是一种模型,如公路铁路交通图,图是一种模型,如公路铁路交通图,水或煤气管网图,通讯联络图等。水或煤气管网图,通讯联络图等。图是对现实的抽象,用点和线的图是对现实的抽象,用点和线的连接组合表示。连接组合表示。6.1 图的基本概念和模型 图不同于几何图形。图不同于几何图形。一、基本概念一、基本概念1、图、图(graph):由:由V,EV,E构成的构成的有序二元组,用以表示对有序二元组,用以表示对某些现实对象及其联系的抽象,记作某些现实对象及其联系的抽象,记作 G=V,E。其中其中V称为点集,记做称为点集,记做V=v1,v2
2、,vn E称为边集,记做称为边集,记做E=e1,e2,em点点(vertex):表示所研究的对象,用:表示所研究的对象,用v v表示;表示;边边(edge):表示对象之间的联系,用:表示对象之间的联系,用e e表示。表示。网络图网络图(赋权图赋权图):点或边具有实际意义点或边具有实际意义(权数权数)的图,的图,记做记做N。零图:零图:边集为空集的图。边集为空集的图。v1v2v3v4v5e1e2e3e4e5e6e7e8特别的,若边特别的,若边e e的两个端点重合,则称的两个端点重合,则称e e为环。为环。若两个端点之间多于一条边,则称为多重边若两个端点之间多于一条边,则称为多重边。2、图的阶:即
3、图中的点数。、图的阶:即图中的点数。例如例如 右图为一个五阶图右图为一个五阶图3、若图中边、若图中边e=vi,vj,则则vi,vj称称为为e的端点,的端点,e称为称为vi,vj的关联边。的关联边。若若vi与与vj是一条边的两个端是一条边的两个端点,则称点,则称vi与与vj相邻;相邻;若边若边ei与与ej有公共的端点,有公共的端点,则称则称ei与与ej相邻。相邻。简单图:无环、无多重边的图。简单图:无环、无多重边的图。例如:例如:e e6 6=v=v2 2,v,v3 3 4 4、点、点v v的次(或度,的次(或度,degreedegree)与点与点v v关联的边的条数,记为关联的边的条数,记为d
4、 dG G(v)(v)或或d(v)d(v)。v1v2v3v4e1e2e3e4e5e6e7v5 悬挂点悬挂点 次为次为1 1的点,如的点,如 v v5 5 悬挂边悬挂边 悬挂点的关联边,如悬挂点的关联边,如 e e8 8e8 孤立点孤立点 次为次为0 0的点的点 偶点偶点 次为偶数的点,如次为偶数的点,如 v v2 2 奇点奇点 次为奇数的点次为奇数的点,如如 v v5 55 5、链:图中保持关联关系的点和边的交替序列,其、链:图中保持关联关系的点和边的交替序列,其中点可重复,但边不能重复。中点可重复,但边不能重复。路:点不能重复的链。路:点不能重复的链。圈:起点和终点重合的链。圈:起点和终点重
5、合的链。回路:起点和终点重合的路。回路:起点和终点重合的路。连通图:任意两点之间至少存在一条链的图。连通图:任意两点之间至少存在一条链的图。完全图:任意两点之间都有边相连的简单图。完全图:任意两点之间都有边相连的简单图。n阶完全图用阶完全图用Kn表示,边数表示,边数=注意:完全图是连通图,但连通图不一定是完全图。注意:完全图是连通图,但连通图不一定是完全图。v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9如图如图(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一条链是一条链,但不是路但不是路(v1,e1,v2,e2,v3,e7,v6
6、,e8,v7)是一条路是一条路(v1,e1,v2,e2,v3,e3,v4,e4,v1)是一个回路是一个回路(v4,e4,v1,e1,v2,e2,v3,e6,v5,e9,v7,e8,v6,e7,v3,e3,v4)是一个圈是一个圈本图是一个连通图。本图是一个连通图。7 7、已知图、已知图G G1 1=V V1 1,E,E1 1,G,G2 2=V V2 2,E,E2 2,若有若有V V1 1 V V2 2,E E1 1 E E2 2,则称,则称G G1 1是是G G2 2的一个子图;的一个子图;若若V V1 1=V=V2 2,E E1 1 E E2 2且且 E E1 1E E2 2,则称,则称G G
7、1 1是是G G2 2的一个部分图。的一个部分图。6 6、偶图(二分图):若图、偶图(二分图):若图G G的点集的点集V V可以分为两个互不可以分为两个互不相交的非空子集相交的非空子集V V1 1和和V V2 2,而且在同一个子集中的点均,而且在同一个子集中的点均互不相邻,则图互不相邻,则图G G称为偶图。称为偶图。完全偶图:完全偶图:V V1 1中的每个点均和中的每个点均和V V2 2中的每个点相邻的偶中的每个点相邻的偶图。图。若完全偶图中若完全偶图中V V1 1有有m m个点,个点,V V2 2有有n n个点,则该图共有个点,则该图共有mn条边。条边。注意:部分图是子图,子图不一定是部分图
8、。注意:部分图是子图,子图不一定是部分图。二、应用例例 有甲、乙、丙、丁、戊、己六名运动员报名有甲、乙、丙、丁、戊、己六名运动员报名参加参加A A、B B、C C、D D、E E、F F六个项目的比赛。如表中所六个项目的比赛。如表中所示,打示,打“”“”的项目是各运动员报名参加比赛的项的项目是各运动员报名参加比赛的项目。问:六个项目的比赛顺序应如何安排,才能做目。问:六个项目的比赛顺序应如何安排,才能做到使每名运动员不连续地参加两项比赛?到使每名运动员不连续地参加两项比赛?甲甲 乙乙 丙丙 丁丁 戊戊 己己项目项目人人ABCDEF解:构造一个六阶图如下:解:构造一个六阶图如下:点:表示运动项目
9、。点:表示运动项目。边:若两个项目之间有同一名运动员报名参加,边:若两个项目之间有同一名运动员报名参加,则对应的两个点之间连一条边。则对应的两个点之间连一条边。ABCDEFACBFEDACBFED为满足题目要求,应为满足题目要求,应该选择不相邻的点来该选择不相邻的点来安排比赛的顺序:安排比赛的顺序:或或D DEFBCAEFBCA6.2 树图和图的最小部分树1 1、树(、树(treetree):无圈的连通图称为树图,简称为):无圈的连通图称为树图,简称为树树,用用T(V,E)T(V,E)或或T T表示。表示。一、树图的概念一、树图的概念2 2、树的性质、树的性质(1 1)树中必有悬挂点。)树中必
10、有悬挂点。证明证明(反证法):(反证法):设树中任何点的次均不为设树中任何点的次均不为1.1.因为树无孤立点,所以树的点的次因为树无孤立点,所以树的点的次2.2.不妨设树有不妨设树有n n个点,记为个点,记为v v1 1,v,v2 2,v,vn n 因为因为d(vd(v1 1)2,)2,不妨设不妨设v v1 1与与v v2 2,v,v3 3相邻。相邻。又因为树没有圈,且又因为树没有圈,且d(vd(v2 2)2,)2,可设可设v v2 2与与v v4 4相邻,相邻,,依次下去,依次下去,v vn n必然与前面的某个点相邻,图中有圈,矛盾!必然与前面的某个点相邻,图中有圈,矛盾!注意:树去掉悬挂点
11、和悬挂边后余下的子图还是树。注意:树去掉悬挂点和悬挂边后余下的子图还是树。(2 2)n n阶树必有阶树必有n-1n-1条边。条边。证明证明(归纳法):(归纳法):当当n=2n=2时,显然;时,显然;设设n=k-1n=k-1时结论成立。时结论成立。当当n=kn=k时,树至少有一个悬挂点。时,树至少有一个悬挂点。去掉该悬挂点和悬挂边,得到一个去掉该悬挂点和悬挂边,得到一个k-1k-1阶的树,它有阶的树,它有k-2k-2条边,则原条边,则原k k阶树有阶树有k-1k-1条边。条边。即即n=kn=k时结论也成立。时结论也成立。综上,综上,n n阶树有阶树有n-1n-1条边。条边。(3 3)任何有)任何
12、有n n个点、个点、n-1n-1条边的连通图是树。条边的连通图是树。证明证明(反证法):(反证法):假设假设n n个点,个点,n-1n-1条边的连通图中有圈,则在该圈中去掉一条边的连通图中有圈,则在该圈中去掉一条边得到的子图仍连通,若子图仍有圈,则继续在相应圈中去条边得到的子图仍连通,若子图仍有圈,则继续在相应圈中去掉一条边,掉一条边,直到得到无圈的连通图,即为树。但是该树有,直到得到无圈的连通图,即为树。但是该树有n n个点,边数少于个点,边数少于n-1,n-1,矛盾!矛盾!注意:注意:树是边数最多的无圈图。树是边数最多的无圈图。树是边数最少的连通图。树是边数最少的连通图。在树中不相邻的两个
13、点之间添上一条边,则恰得到一个圈。在树中不相邻的两个点之间添上一条边,则恰得到一个圈。从树中去掉一条边,则余下的图不连通。从树中去掉一条边,则余下的图不连通。3、图的最小部分树(1 1)部分树:若)部分树:若G G1 1是是G G2 2的一个部分图,且的一个部分图,且G1G1为树,为树,则称则称G G1 1是是G G2 2的一个部分树(或支撑树)。的一个部分树(或支撑树)。G2:ABCD547365576G1:ACBD注意:注意:图图G有部分树的必要条件是有部分树的必要条件是G是连通图。是连通图。部分树不是唯一的。部分树不是唯一的。(2 2)最小部分树(或最小支撑树)最小部分树(或最小支撑树)
14、图图G G为网络图,若为网络图,若T T是部分树中权和最小者,则是部分树中权和最小者,则称称T T是是G G的最小部分树的最小部分树(或称最小支撑树或称最小支撑树).).二、最小部分树的求法二、最小部分树的求法1 1、原理、原理(1 1)图中与点)图中与点v v关联的最短边(即权最小的边)一关联的最短边(即权最小的边)一定包含在最小部分树中。定包含在最小部分树中。(2 2)将图中的点分成两个互不相交的非空子集,则)将图中的点分成两个互不相交的非空子集,则两个子集之间连线的最短边一定包含在最小部分树两个子集之间连线的最短边一定包含在最小部分树中。中。SABCDET252414317557即求图中
15、的最小部分树即求图中的最小部分树例:要在下图所示的各个位置之间建立起通信网络,例:要在下图所示的各个位置之间建立起通信网络,试确定使总距离最小的方案。试确定使总距离最小的方案。2 2、求法、求法方法一:方法一:避圈法避圈法 将图中所有的点分将图中所有的点分V V为为V V两部分,两部分,VV最小部分树中的点的集合最小部分树中的点的集合 VV非最小部分树中的点的集合非最小部分树中的点的集合 任取一点任取一点vi,令,令viV,其他点在,其他点在V中中 在在V与与V相连的边中取一条最短的边相连的边中取一条最短的边(vi,vj),加粗加粗(vi,vj),令,令vjV,并在,并在V中去掉中去掉vj 重
16、复重复,至所有的点均在,至所有的点均在V之内。之内。“取小边取小边”避圈法另一种做法避圈法另一种做法:1.1.在所有各边中找到边权最小的一条,将其作在所有各边中找到边权最小的一条,将其作为最小部分树中的第一边;在剩余的边中,仍然找为最小部分树中的第一边;在剩余的边中,仍然找到边权最小的作为最小部分树的第二条边;到边权最小的作为最小部分树的第二条边;2.2.在剩余的边中,找到边权最小的边,查看其在剩余的边中,找到边权最小的边,查看其是否与前面的边形成圈,如果没有,则在最小部分是否与前面的边形成圈,如果没有,则在最小部分树中添加该边,如果形成了圈,则不再考虑该边;树中添加该边,如果形成了圈,则不再
17、考虑该边;3.3.重复进行第二步,直到找到第重复进行第二步,直到找到第 n-1 n-1 条边为条边为止。(因为有止。(因为有 n n 个顶点的树中一定有个顶点的树中一定有 n-1 n-1 条边)条边)例:分别用两种避圈法构造下图的最小部分树。例:分别用两种避圈法构造下图的最小部分树。第一种解法:第一种解法:1.1.在点集中任选一点,不妨取在点集中任选一点,不妨取 S S,令令 V=SV=S 2.2.找到和找到和 S S 相邻的边中,权值最小的相邻的边中,权值最小的 S,A S,A。3.3.V=S,AV=S,A 4.4.重复第重复第2 2,3 3步,找到下一个点。步,找到下一个点。第二种做法求解
18、过程:第二种做法求解过程:方法二:破圈法求解步骤:方法二:破圈法求解步骤:1.1.从图从图 N N 中任取一回路,去掉这个回路中边权最大中任取一回路,去掉这个回路中边权最大的边,得到原图的一个子图的边,得到原图的一个子图 N1N1。2.2.从剩余的子图中任找一回路,同样去掉回路中边从剩余的子图中任找一回路,同样去掉回路中边权最大的一条边,得一新的子图;权最大的一条边,得一新的子图;3.3.重复第重复第 2 2 步,直到图中不再含有回路为止。步,直到图中不再含有回路为止。用破圈法求解上例:用破圈法求解上例:1.1.任意找到一回路,不妨取任意找到一回路,不妨取 DETDDETD,去掉边权最大的去掉
19、边权最大的边边 T,E;T,E;2.2.从剩余的子图中任找一回路,同样去掉回路中边从剩余的子图中任找一回路,同样去掉回路中边权最大的一条边,得一新的子图;依次类推。权最大的一条边,得一新的子图;依次类推。破圈法的另一种解法:破圈法的另一种解法:1.1.从剩余图中找到边权最大的一条边,如果将其删从剩余图中找到边权最大的一条边,如果将其删除后图仍然是连通的,则删除此边,否则不再考虑此边;除后图仍然是连通的,则删除此边,否则不再考虑此边;2.2.重复上述步骤,直到剩余边数为重复上述步骤,直到剩余边数为 n-1 n-1 为止。为止。用此法求解上述问题:用此法求解上述问题:注意:注意:1.1.一个图的最
20、小部分树不唯一,该题中用几种解法一个图的最小部分树不唯一,该题中用几种解法得到的结果都是相同的,是特殊情况;得到的结果都是相同的,是特殊情况;2.2.不同解法得到的最小部分树所包含的边虽然可能不同解法得到的最小部分树所包含的边虽然可能不相同,但是,每个最小部分树中所有边权的总和一定都不相同,但是,每个最小部分树中所有边权的总和一定都是相同的,即都达到了最小。是相同的,即都达到了最小。6.3 最短路问题1 1、最短路问题、最短路问题 从已知的网络图中找出两点之间距离最短(即权和从已知的网络图中找出两点之间距离最短(即权和最小)的路。最小)的路。2 2、相关记号、相关记号(1 1)dij表示图中两
21、个相邻点表示图中两个相邻点i i和和j j之间的距离(即权)。之间的距离(即权)。易见易见 dii=0=0 约定:当约定:当i i和和j j不相邻时,不相邻时,dij=(2 2)Lij表示图中点表示图中点i i和和j j之间的最短距离(即最小权和)。之间的最短距离(即最小权和)。易见易见 Lii=0 =0 即在已知的网络图中,从给定点即在已知的网络图中,从给定点s s出发,要到达目出发,要到达目的地的地t t。问:选择怎样的行走路线,可使总行程最短?。问:选择怎样的行走路线,可使总行程最短?3 3、狄克斯屈拉(、狄克斯屈拉(Dijkstra)标号算法)标号算法(1 1)适用范围)适用范围 用于
22、求某两个点之间的最短距离。用于求某两个点之间的最短距离。(2 2)原理)原理 最短路上任何片段是最短路。最短路上任何片段是最短路。v1 v2 v3 v4v5(3 3)思想)思想 按离出发点按离出发点s的距离由近至远逐步标出最短距离的距离由近至远逐步标出最短距离Lsi以及最佳行进路线。以及最佳行进路线。SABCDET252414317557例例 求图中求图中S到到T的最短路及最短距离。的最短路及最短距离。(4 4)步骤)步骤 在网络图中求在网络图中求s到到t的最短路。的最短路。第一步第一步 从从s出发,将出发,将Lss=0标记在标记在s旁边的方框内旁边的方框内(表示点(表示点s已标记);已标记)
23、;第二步第二步 找出与找出与s相邻且距离最小的点,设为相邻且距离最小的点,设为r,计算,计算Lsr=Lss+dsr,并将结果标记在,并将结果标记在r旁边的方框内旁边的方框内(表示点(表示点r r已标记),同时标记边已标记),同时标记边srsr;第三步第三步 从已标记的点出发,找出这些点的所有未从已标记的点出发,找出这些点的所有未标记邻点,分别计算已标记点的方框数与其邻点的距标记邻点,分别计算已标记点的方框数与其邻点的距离之和,利用离之和,利用“叠加最小叠加最小”的原则确定下一个被标记的原则确定下一个被标记点,设为点,设为p p,并将最小的和标记在,并将最小的和标记在p p旁边的方框内(表旁边的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 应用 第五 胡运权
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。