《运筹学基础及应用第五版ppt课件》由会员分享，可在线阅读，更多相关《运筹学基础及应用第五版ppt课件（59页珍藏版）》请在金锄头文库上搜索。
1、第6章 图与网络分析Graph and Network Analysis. 图是一种模型，如公路铁路交通图，图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。水或煤气管网图，通讯联络图等。 图是对现实的抽象，用点和线的图是对现实的抽象，用点和线的连接组合表示。连接组合表示。6.1 图的基本概念和模型 图不同于几何图形。图不同于几何图形。.一、基本概念一、基本概念1、图、图(graph)：由：由V,EV,E构成的构成的有序二元组，用以表示对有序二元组，用以表示对某些现实对象及其联系的抽象，记作某些现实对象及其联系的抽象，记作 G=V,E。 其中其中V称为点集，记做称为点集，记做V=v
2、1,v2,vn E称为边集，记做称为边集，记做E=e1,e2,em点点( (vertex) )：表示所研究的对象，用：表示所研究的对象，用v v表示；表示； 边边( (edge) )：表示对象之间的联系，用：表示对象之间的联系，用e e表示。表示。网络图网络图(赋权图赋权图)： 点或边具有实际意义点或边具有实际意义(权数权数)的图，的图，记做记做N。零图：零图： 边集为空集的图。边集为空集的图。.v1v2v3v4v5e1e2e3e4e5e6e7e8特别的，若边特别的，若边e e的两个端点重合，则称的两个端点重合，则称e e为环。为环。 若两个端点之间多于一条边，则称为多重边若两个端点之间多于一
3、条边，则称为多重边。2、图的阶：即图中的点数。、图的阶：即图中的点数。例如例如 右图为一个五阶图右图为一个五阶图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） 与点
4、与点v v关联的边的条数，记为关联的边的条数，记为d dG G(v)(v)或或d(v)d(v)。v1v2v3v4e1e2e3e4e5e6e7v5 悬挂点悬挂点 次为次为1 1的点，如的点，如 v v5 5 悬挂边悬挂边 悬挂点的关联边，如悬挂点的关联边，如 e e8 8e8 孤立点孤立点 次为次为0 0的点的点 偶点偶点 次为偶数的点，如次为偶数的点，如 v v2 2 奇点奇点 次为奇数的点次为奇数的点, , 如如 v v5 5.5 5、链：图中保持关联关系的点和边的交替序列，其、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。中点可重复，但边不能重复。路：点不能重复的链。
5、路：点不能重复的链。圈：起点和终点重合的链。圈：起点和终点重合的链。回路：起点和终点重合的路。回路：起点和终点重合的路。连通图：任意两点之间至少存在一条链的图。连通图：任意两点之间至少存在一条链的图。完全图：任意两点之间都有边相连的简单图。完全图：任意两点之间都有边相连的简单图。 n阶完全图用阶完全图用Kn表示，边数表示，边数=注意：完全图是连通图，但连通图不一定是完全图。注意：完全图是连通图，但连通图不一定是完全图。.v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9如图如图(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一条链是一
6、条链, 但不是路但不是路(v1,e1,v2,e2,v3,e7,v6,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
7、=V=V2 2，E E1 1 E E2 2且且 E E1 1E E2 2 ，则称，则称G G1 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有有
8、n n个点，则该图共有个点，则该图共有mn条边。条边。注意：部分图是子图，子图不一定是部分图。注意：部分图是子图，子图不一定是部分图。.二、应用例例 有甲、乙、丙、丁、戊、己六名运动员报名有甲、乙、丙、丁、戊、己六名运动员报名参加参加A A、B B、C C、D D、E E、F F六个项目的比赛。如表中所六个项目的比赛。如表中所示，打示，打“”“”的项目是各运动员报名参加比赛的项的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？到使每名运动员不连续地参加两项比赛？甲甲 乙乙 丙丙 丁丁 戊戊
9、 己己项目项目人人ABCDEF.解：构造一个六阶图如下：解：构造一个六阶图如下： 点：表示运动项目。点：表示运动项目。边：若两个项目之间有同一名运动员报名参加，边：若两个项目之间有同一名运动员报名参加，则对应的两个点之间连一条边。则对应的两个点之间连一条边。ABCDEFACBFEDACBFED为满足题目要求，应为满足题目要求，应该选择不相邻的点来该选择不相邻的点来安排比赛的顺序：安排比赛的顺序：或或D DEFBCAEFBCA.6.2 树图和图的最小部分树1 1、树（、树（treetree）：无圈的连通图称为树图，简称为）：无圈的连通图称为树图，简称为树树, ,用用T(V,E)T(V,E)或或T
10、 T表示。表示。一、树图的概念一、树图的概念.2 2、树的性质、树的性质（1 1）树中必有悬挂点。）树中必有悬挂点。证明证明（反证法）：（反证法）： 设树中任何点的次均不为设树中任何点的次均不为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相邻，相邻，, , 依次下去，
11、依次下去，v vn n必然与前面的某个点相邻，图中有圈，矛盾！必然与前面的某个点相邻，图中有圈，矛盾！注意：树去掉悬挂点和悬挂边后余下的子图还是树。注意：树去掉悬挂点和悬挂边后余下的子图还是树。.（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条
12、边。条边。 即即n=kn=k时结论也成立。时结论也成立。 综上，综上，n n阶树有阶树有n-1n-1条边。条边。 .（3 3）任何有）任何有n n个点、个点、n-1n-1条边的连通图是树。条边的连通图是树。证明证明（反证法）：（反证法）： 假设假设n n个点，个点，n-1n-1条边的连通图中有圈，则在该圈中去掉一条边的连通图中有圈，则在该圈中去掉一条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去掉一条边，掉一条边，直到得到无圈的连通图，即为树。但是该树有，直到得到无圈的连通图，即为树。但是该树有n n个点，边数少于个点，边数少于n-1
13、,n-1,矛盾！矛盾！ 注意：注意： 树是边数最多的无圈图。树是边数最多的无圈图。 树是边数最少的连通图。树是边数最少的连通图。在树中不相邻的两个点之间添上一条边，则恰得到一个圈。在树中不相邻的两个点之间添上一条边，则恰得到一个圈。 从树中去掉一条边，则余下的图不连通。从树中去掉一条边，则余下的图不连通。.3、图的最小部分树（1 1）部分树：若）部分树：若G G1 1是是G G2 2的一个部分图，且的一个部分图，且G1G1为树，为树，则称则称G G1 1是是G G2 2的一个部分树（或支撑树）。的一个部分树（或支撑树）。G2：ABCD547365576G1：ACBD注意：注意： 图图G有部分树
14、的必要条件是有部分树的必要条件是G是连通图。是连通图。 部分树不是唯一的。部分树不是唯一的。.（2 2）最小部分树（或最小支撑树）最小部分树（或最小支撑树） 图图G G为网络图，若为网络图，若T T是部分树中权和最小者，则是部分树中权和最小者，则称称T T是是G G的最小部分树的最小部分树( (或称最小支撑树或称最小支撑树).).二、最小部分树的求法二、最小部分树的求法1 1、原理、原理（1 1）图中与点）图中与点v v关联的最短边（即权最小的边）一关联的最短边（即权最小的边）一定包含在最小部分树中。定包含在最小部分树中。（2 2）将图中的点分成两个互不相交的非空子集，则）将图中的点分成两个互
15、不相交的非空子集，则两个子集之间连线的最短边一定包含在最小部分树两个子集之间连线的最短边一定包含在最小部分树中。中。.SABCDET252414317557即求图中的最小部分树即求图中的最小部分树例：要在下图所示的各个位置之间建立起通信网络，例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最小的方案。试确定使总距离最小的方案。.2 2、求法、求法方法一：方法一： 避圈法避圈法 将图中所有的点分将图中所有的点分V V为为V V两部分，两部分，VV最小部分树中的点的集合最小部分树中的点的集合 VV非最小部分树中的点的集合非最小部分树中的点的集合 任取一点任取一点vi，令，令viV，其他
16、点在，其他点在V中中 在在V与与V相连的边中取一条最短的边相连的边中取一条最短的边(vi,vj)， 加粗加粗(vi,vj)，令，令vjV ，并在，并在V中去掉中去掉vj 重复重复 ，至所有的点均在，至所有的点均在V之内。之内。“取小边取小边”. 避圈法另一种做法避圈法另一种做法： 1. 1. 在所有各边中找到边权最小的一条，将其作在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；边权最小的作为最小部分树的第二条边； 2. 2. 在剩余的边中，找到边权最小的边，查看其在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；树中添加该边，如果形成了圈，则不再考虑该边； 3. 3. 重复进行第二步，直到找到第重复进行第二步，直到找到第 n-1 n-1 条边为条边为止。（因为有止。（因为有 n n 个顶点的树中一定有个顶点的树中一定有 n-1 n-1 条边）条边）.
