运筹学胡运权第五版课件(第6章).ppt

《运筹学胡运权第五版课件(第6章).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章图与网络分析GraphandNetworkAnalysis图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。图是对现实的抽象，用点和线的连接组合表示。§6.1图的基本概念和模型图不同于几何图形。一、基本概念1、图(graph)：由V,E构成的有序二元组，用以表示对某些现实对象及其联系的抽象，记作G=｛V,E｝。其中V称为点集，记做V=｛v1,v2,···,vn｝E称为边集，记做E=｛e1,e2,···,em｝点(vertex)：表示所研究的对象，用v表示；边(edge)：表示对象之间的联系，用e表示。网络图(赋

2、权图)：点或边具有实际意义(权数)的图，记做N。零图：边集为空集的图。v1v2v3v4v5e1e2e3e4e5e6e7e8特别的，若边e的两个端点重合，则称e为环。若两个端点之间多于一条边，则称为多重边。2、图的阶：即图中的点数。例如右图为一个五阶图3、若图中边e=[vi,vj],则vi,vj称为e的端点，e称为vi,vj的关联边。若vi与vj是一条边的两个端点，则称vi与vj相邻；若边ei与ej有公共的端点，则称ei与ej相邻。简单图：无环、无多重边的图。例如：e6=[v2,v3]4、点v的次（或度，degree）与点v关联的

3、边的条数，记为dG(v)或d(v)。v1v2v3v4e1e2e3e4e5e6e7v5悬挂点次为1的点，如v5悬挂边悬挂点的关联边，如e8e8孤立点次为0的点偶点次为偶数的点，如v2奇点次为奇数的点,如v55、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。路：点不能重复的链。圈：起点和终点重合的链。回路：起点和终点重合的路。连通图：任意两点之间至少存在一条链的图。完全图：任意两点之间都有边相连的简单图。n阶完全图用Kn表示，边数=注意：完全图是连通图，但连通图不一定是完全图。v1v2v5v6v7v3v4e1e

4、2e4e3e5e6e7e8e9如图(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一条链,但不是路(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、已知图G1=｛V1,E1｝,G2={V2,E2},若有V1V2，E1E2，则称G1是G2的一个子图；若V1=V2，E1E

5、2且E1≠E2，则称G1是G2的一个部分图。6、偶图（二分图）：若图G的点集V可以分为两个互不相交的非空子集V1和V2，而且在同一个子集中的点均互不相邻，则图G称为偶图。完全偶图：V1中的每个点均和V2中的每个点相邻的偶图。若完全偶图中V1有m个点，V2有n个点，则该图共有mn条边。注意：部分图是子图，子图不一定是部分图。二、应用例有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“√”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参

6、加两项比赛？甲乙丙丁戊己项目人ABCDEF√√√√√√√√√√√√√√√√解：构造一个六阶图如下：点：表示运动项目。边：若两个项目之间有同一名运动员报名参加，则对应的两个点之间连一条边。ABCDEFA—C—B—F—E—D为满足题目要求，应该选择不相邻的点来安排比赛的顺序：或D—E—F—B—C—A§6.2树图和图的最小部分树1、树（tree）：无圈的连通图称为树图，简称为树,用T(V,E)或T表示。一、树图的概念2、树的性质（1）树中必有悬挂点。证明（反证法）：设树中任何点的次均不为1.因为树无孤立点，所以树的点的次≥2.不妨设树

7、有n个点，记为v1,v2,…,vn因为d(v1)≥2,不妨设v1与v2,v3相邻。又因为树没有圈，且d(v2)≥2,可设v2与v4相邻，…,依次下去，vn必然与前面的某个点相邻，图中有圈，矛盾！注意：树去掉悬挂点和悬挂边后余下的子图还是树。（2）n阶树必有n-1条边。证明（归纳法）：当n=2时，显然；设n=k-1时结论成立。当n=k时，树至少有一个悬挂点。去掉该悬挂点和悬挂边，得到一个k-1阶的树，它有k-2条边，则原k阶树有k-1条边。即n=k时结论也成立。综上，n阶树有n-1条边。（3）任何有n个点、n-1条边的连通图是树。

8、证明（反证法）：假设n个点，n-1条边的连通图中有圈，则在该圈中去掉一条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去掉一条边，…，直到得到无圈的连通图，即为树。但是该树有n个点，边数少于n-1,矛盾！注意：①树是边数最多的无圈图。②树是边数最少的连通图。