《运筹学课件 图与网络分析》由会员分享，可在线阅读，更多相关《运筹学课件 图与网络分析（67页珍藏版）》请在金锄头文库上搜索。
1、运筹学教程引言引言图论是专门研究图的理论的一门数学分图论是专门研究图的理论的一门数学分 支，属于离散数学范畴，与运筹学有交叉，支，属于离散数学范畴，与运筹学有交叉， 它有它有200200多年历史，大体可划分为多年历史，大体可划分为三个阶段三个阶段： 第一阶段第一阶段是从十八世纪中叶到十九世纪中叶是从十八世纪中叶到十九世纪中叶 ，处于萌芽阶段，多数问题围游戏而产生，处于萌芽阶段，多数问题围游戏而产生， 最有代表性的工作是所谓的最有代表性的工作是所谓的EulerEuler七桥问题，七桥问题， 即一笔画问题。即一笔画问题。第八章第八章 图与网络分析图与网络分析运筹学教程第二阶段第二阶段是从十九世纪中
2、叶到二十世纪是从十九世纪中叶到二十世纪 中叶，这时，图论问题大量出现，如中叶，这时，图论问题大量出现，如 HamiltonHamilton问题，地图染色的四色问题以问题，地图染色的四色问题以 及可平面性问题等，这时，也出现用图及可平面性问题等，这时，也出现用图 解决实际问题，如解决实际问题，如CayleyCayley把树应用于化把树应用于化 学领域，学领域，KirchhoffKirchhoff用树去研究电网络等用树去研究电网络等.运筹学教程第三阶段第三阶段是二十世纪中叶以后，由生产管理是二十世纪中叶以后，由生产管理 、军事、交通、运输、计算机网络等方面提、军事、交通、运输、计算机网络等方面提
3、出实际问题，以及大型计算机使大规模问题出实际问题，以及大型计算机使大规模问题 的求解成为可能，特别是以的求解成为可能，特别是以FordFord和和 FulkersonFulkerson建立的网络流理论，与线性规划建立的网络流理论，与线性规划 、动态规划等优化理论和方法相互渗透，促、动态规划等优化理论和方法相互渗透，促 进了图论对实际问题的应用。进了图论对实际问题的应用。运筹学教程例：例：哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一哥尼斯堡（现名加里宁格勒）是欧洲一 个城市，个城市，PregeiPregei河把该城分成两部分，河中河把该城分成两部分，河中 有两个小岛，十八世
4、纪时，河两边及小岛之有两个小岛，十八世纪时，河两边及小岛之 间共有七座桥，当时人们提出这样的问题：间共有七座桥，当时人们提出这样的问题： 有没有办法从某处（如有没有办法从某处（如A A）出发，经过各桥出发，经过各桥 一次且仅一次最后回到原地呢？一次且仅一次最后回到原地呢？运筹学教程A AB BC CD D运筹学教程最后，数学家最后，数学家EulerEuler在在17361736年巧妙地给出年巧妙地给出 了这个问题的答案，并因此奠定了图论的基了这个问题的答案，并因此奠定了图论的基 础，础，EulerEuler把把A A、B B、C C、D D四块陆地分别收缩四块陆地分别收缩 成四个顶点，把桥表示
5、成连接对应顶点之间成四个顶点，把桥表示成连接对应顶点之间 的边，问题转化为从任意一点出发，能不能的边，问题转化为从任意一点出发，能不能 经过各边一次且仅一次，最后返回该点。这经过各边一次且仅一次，最后返回该点。这 就是著名的就是著名的EulerEuler问题。问题。运筹学教程A AC CB BD D运筹学教程例：例：哈密顿（哈密顿（HamiltonHamilton）回路是十九世回路是十九世 纪英国数学家哈密顿提出，给出一个正纪英国数学家哈密顿提出，给出一个正 1212面体图形，共有面体图形，共有2020个顶点表示个顶点表示2020个城个城 市，要求从某个城市出发沿着棱线寻找市，要求从某个城市出
6、发沿着棱线寻找 一条经过每个城市一次而且仅一次，最一条经过每个城市一次而且仅一次，最 后回到原处的周游世界线路（并不要求后回到原处的周游世界线路（并不要求 经过每条边）。经过每条边）。运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程图的基本概念图的基本概念图论是专门研究图的理论的一图论是专门研究图的理论的一 门数学分支，主要研究点和线之间的门数学分支，主要研究点和线之间的 几何关系。几何关系。运筹学教程一、图与网络的基本概念一、图与网络的基本概念1 1、图及其分类
7、、图及其分类定义定义1 1：（图）一个图由点集：（图）一个图由点集V V和和V V中的元素无序对的一个中的元素无序对的一个 集合，记为集合，记为 G=G=（V V，E E）其中：其中：V= V= （ v v1 1， v v2 2，. . v vmm）是）是mm个顶点集合；个顶点集合；E= E= （ e e1 1， e e2 2，. e. en n） 是是n n条边集合。条边集合。当当V V和和E E为有限集合时，为有限集合时，GG为有限图。为有限图。2 2个点个点u,vu,v属于属于V V，如果边如果边(u,v)(u,v)属于属于E E， u,vu,v相邻相邻；u,vu,v为边为边(u,v)(
8、u,v)的的端点端点。具有公共端点具有公共端点u u的两条边，称为点的两条边，称为点u u的的关联边。关联边。第一节第一节 图与网络的基本知识图与网络的基本知识运筹学教程如果任一边如果任一边(u,v)(u,v)属于属于E E且端点无序，且端点无序，无向边无向边；图；图GG为为无向图无向图 。如果任一边如果任一边(u,v)(u,v)属于属于E E且端点有序，且端点有序，有向边有向边；图；图GG为为有向图有向图m(Gm(G)= E )= E ，表示图表示图GG的边数；的边数；n(G)= V n(G)= V ，表示图表示图GG的点数；的点数；运筹学教程环（自回路）：一条边的两个端点如果相同。环（自回
9、路）：一条边的两个端点如果相同。两个点之间多于一条边的，多重边。两个点之间多于一条边的，多重边。定义定义2 2：不含环和多重边的图，简单图。：不含环和多重边的图，简单图。含有多重边的图，多重图。含有多重边的图，多重图。有向图中的两点之间有不同方向的两条边，不是多重边。有向图中的两点之间有不同方向的两条边，不是多重边。简单图运筹学教程定义定义3 3：每一对顶点间都有边相连的无向简单图，完全图。每一对顶点间都有边相连的无向简单图，完全图。有向完全图：指每一对顶点间有且仅有一条有向边的简单有向完全图：指每一对顶点间有且仅有一条有向边的简单 图。图。定义定义4:4:图图G=(V,E)G=(V,E)的点
10、集的点集V V可以分为可以分为2 2个非空子集个非空子集X,YX,Y，使得使得 E E中每条边的两个端点必有一个端点属于中每条边的两个端点必有一个端点属于X X，另一个端点属另一个端点属 于于Y Y，GG为二部图（偶图），有时记为：为二部图（偶图），有时记为： G=(X,Y,E)G=(X,Y,E)V1V4V3V2XY运筹学教程2、顶点的次 定义5：以点以点v v为端点的边的个数称为点为端点的边的个数称为点v v的次，记作的次，记作d(v)d(v), ,如次为零的点称为弧立点；如次为零的点称为弧立点；次为次为1 1的点称为悬挂点。悬挂点的边称为悬挂边。的点称为悬挂点。悬挂点的边称为悬挂边。次为奇
11、数的点称为奇点，次为偶数的点称为偶点。次为奇数的点称为奇点，次为偶数的点称为偶点。偶点：偶点：d(d(v v) )= =偶数；偶数；奇点：奇点：d d( (v v) )= =奇数；奇数；运筹学教程v1v1v3v3v2v2v4v4v6v6v5v5e1e1e3e3 e5e5e6e6e4e4e8e8e7e7e2e2运筹学教程V= V= （ v v1 1， v v2 2，. v. v6 6）E= E= （ e e1 1， e e2 2，. e. e8 8）（e e1 1）= = （v v1 1， v v2 2）（e e2 2）= = （v v1 1， v v2 2）（e e7 7）= = （v v3
12、3， v v5 5）（e e8 8）= = （v v4 4， v v4 4）(e(e8 8)= (v)= (v4 4， v v4 4), ),称为自回路称为自回路( (环环) )；v v6 6是孤立点，是孤立点，v v5 5为悬挂点，为悬挂点，e e7 7为悬挂边，顶点为悬挂边，顶点v v3 3的次为的次为 4 4，顶点，顶点v v4 4的次为的次为4 4。运筹学教程定理定理1 1 在一个图中，所有顶点次的和等于边的两倍在一个图中，所有顶点次的和等于边的两倍 。定理定理2 2 在任意一个图中，次为奇数的顶点必为偶数在任意一个图中，次为奇数的顶点必为偶数 个。个。定义定义6 6：有向图中，以：有
13、向图中，以v vi i为始点的边数称为点为始点的边数称为点v vi i的的出出 次，次，d d+ +(v(vi i); ); 以以v vi i为为终点的边数称为点终点的边数称为点v vi i的的入次，入次，d d- -(v(vi i); );所有顶点的入次之和所有顶点的入次之和= =所有顶点的出次之和；所有顶点的出次之和；运筹学教程3 3、子图、子图定义定义：设：设G=G=（V V，E E）和）和GG1 1= =（V V1 1，E E1 1）。）。如果如果V V1 1 V V， E E1 1 E E则称则称GG1 1为为GG的子图；的子图；如果如果GG1 1 = =（ V V1 1，E E1
14、1 ）是）是G=G=（V V，E E）子图子图 ，并且，并且V V1 1 = = V V，则称则称GG1 1为为GG的生成子图；的生成子图；运筹学教程v1v1v5v5v4v4v2v2v3v3 e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2运筹学教程v1v1v5v5v4v4v2v2 e1e1e5e5e3e3（a a） 的子图的子图运筹学教程v1v1v5v5v4v4v2v2v3v3e8e8e6e6e5e5e2e2（a a）的生的生 成子图成子图运筹学教程二、连通图二、连通图定义定义8:8:如果图中的某些点、边可以排列成点和边的交错序列如果图中的某些点、边可以排列成点和边的交错序列
15、( (v v0 0 ,e ,e1 1 ,v ,v1 1 ,e ,e2 2 ,v ,v2 2，e e3 3 ,v ,v3 3 ,v,vn-1 n-1 , e, en n ， v vn n ），e ei i=(v=(vi-1i-1,v ,vi i) )，则称则称 此为一条链。此为一条链。由两两相邻的点及其相关联边构成的点边序列。由两两相邻的点及其相关联边构成的点边序列。初等链：链中无重复的点和边；定义定义9 9：无向图中，如一条链中起点和终点重合，则称此链为无向图中，如一条链中起点和终点重合，则称此链为 圈。圈。初等圈：圈中无重复的点和边；有向图中，当有向图中，当链（圈）链（圈）上的边方向相同时，
16、为上的边方向相同时，为道路（回路）道路（回路） 。运筹学教程道路道路回路链初等链初等圈链、初等链、初等圈链、初等链、初等圈道路、回路道路、回路运筹学教程连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。运筹学教程v1v1v5v5v4v4v2v2v3v3 e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3 e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3 e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图运筹学教程v1v1v5v5v4v4
