运筹学 --图与网络1(qh).ppt
《运筹学 --图与网络1(qh).ppt》由会员分享,可在线阅读,更多相关《运筹学 --图与网络1(qh).ppt(201页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第十章第十章图与网络分析图与网络分析引言引言图图论论是是专专门门研研究究图图的的理理论论的的一一门门数数学学分分支支,属属于于离离散散数数学学范范畴畴,与与运运筹筹学学有有交交叉叉,它它有有200多多年年历历史史,大大体体可可划划分分为为三三个个阶阶段段:第第一一阶阶段段是是从从十十八八世世纪纪中中叶叶到到十十九九世世纪纪中中叶叶,处处于于萌萌芽芽阶阶段段,多多数数问问题题为为游游戏戏而而产产生生,最最有有代代表表性性的的工工作作是是所所谓谓的的Euler七七桥桥问问题题(1736年年),即即一一笔笔画画问题。问题。第第二二阶阶段段是是从从十十九九世世纪纪中中叶叶到到二二十十世世纪纪中中叶叶,
2、这这时时,图图论论问问题题大大量量出出现现,如如Hamilton问问题题,地地图图染染色色的的四四色色问问题题以以及及可可平平面面性性问问题题等等,这这时时,也也出出现现用用图图解解决决实实际际问问题题,如如Cayley把把树树应应用用于于化化学学领领域域,Kirchhoff用用树树去去研研究究电电网络等网络等.第第三三阶阶段段是是二二十十世世纪纪中中叶叶以以后后,由由生生产产管管理理、军军事事、交交通通、运运输输、计计算算机机网网络络等等方方面面提提出出实实际际问问题题,以以及及大大型型计计算算机机使使大大规规模模问问题题的的求求解解成成 为为 可可 能能,特特 别别 是是 以以 Ford和
3、和Fulkerson建建立立的的网网络络流流理理论论,与与线线性性规规划划、动动态态规规划划等等优优化化理理论论和和方方法法相相互互渗渗透透,促促进进了了图图论论对对实实际际问题的应用。问题的应用。例例10-1:哥尼斯堡七桥问题哥尼斯堡七桥问题哥哥尼尼斯斯堡堡(现现名名加加里里宁宁格格勒勒)是是欧欧洲洲一一个个城城市市,Pregei河河把把该该城城分分成成两两部部分分,河河中中有有两两个个小小岛岛,十十八八世世纪纪时时,河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥,当当时时人人们们提提出出这这样样的的问问题题:有有没没有有办办法法从从某某处处(如如A)出出发发,经经过过各各桥桥一一次次
4、且且仅仅一一次次最最后后回回到到原原地呢?地呢?ABCD最最后后,数数学学家家Euler在在1736年年巧巧妙妙地地给给出出了了这这个个问问题题的的答答案案,并并因因此此奠奠定定了了图图论论的的基基础础,Euler把把A、B、C、D四四块块陆陆地地分分别别收收缩缩成成四四个个顶顶点点,把把桥桥表表示示成成连连接接对对应应顶顶点点之之间间的的边边,问问题题转转化化为为从从任任意意一一点点出出发发,能能不不能能经经过过各各边边一一次次且且仅仅一一次次,最最后后返返回回该该点点。这这就就是是著著名名的的Euler问题。问题。ACBD例例10-2:有有7个个人人围围桌桌而而坐坐,如如果果要要求求每每次
5、次相相邻邻的的人人都都与与以以前前完完全全不不同同,试试问问不不同同的的就就座座方方案案共共有有多少种?多少种?用用顶顶点点表表示示人人,用用边边表表示示两两者者相相邻邻,因因为为最最初初任任何何两两个个人人都都允允许许相相邻邻,所所以以任任何何两两点点都都可可以以有边相连。有边相连。1 12 23 37 76 64 45 5假定第一次就座方案是假定第一次就座方案是(1,2,3,4,5,6,7,1),那那么么第第二二次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻,只只能能从从图图中删去这些边。中删去这些边。1 12 23 37 76 64 45 51 12 23
6、37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5假定第二次就座方案是假定第二次就座方案是(1,3,5,7,2,4,6,1),那那么么第第三三次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻,只只能能从图中删去这些边。从图中删去这些边。1 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 7
7、6 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5假定第三次就座方案是假定第三次就座方案是(1,4,7,3,6,2,5,1),那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻,只只能能从从图图中中删删去去这这些些边边,只只留留下下7点点孤孤立立点点,所所以以该该问问题题只只有有三三个个就就座座方方案。案。1 12 23 37 76 64 45 51 12 23 37 76 6
8、4 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5例例10-3:哈哈密密顿顿(Hamilton)回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出,给给出出一一个个正正12面面体体图图形形,共共有有20个个顶顶点点表表示示20个个城城市市,要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次,最最后
9、后回回到到原原处处的的周周游游世世界界线线路(并不要求经过每条边)。路(并不要求经过每条边)。一.有甲、乙、丙、丁、戊、己6名运动员报名参加A,B,C,D,E,F,6项比赛。下表给出6个运动员报名参加的比赛项目。问6个项目比赛顺序如何安排,做到每名运动员不连续参加两项比赛。甲乙丙丁戊己ABCDEF解解:比赛项目作为点比赛项目作为点,两个比赛项目由同一个人参加连一边两个比赛项目由同一个人参加连一边.如图如图:ABDFCE比赛顺序可安排A-C-B-F-E-D或A-F-B-C-D-E甲乙丙丁戊己ABCDEF10.1 10.1 图的基本概念图的基本概念图论是专门研究图的理图论是专门研究图的理论的一门数
10、学分支,主要研论的一门数学分支,主要研究点和线之间的究点和线之间的几何关系。几何关系。定义定义:(图):(图)设设G=(V,E,)其中:其中:V=(v1,v2,.vm)是是m个顶点集合;个顶点集合;E=(e1,e2,.en)是是n条边集合。条边集合。是描述边与顶点之间关系的函数是描述边与顶点之间关系的函数称称称称G=G=(V V,E E,)为为为为 一个图,如果它满足:一个图,如果它满足:一个图,如果它满足:一个图,如果它满足:(1 1)V V非空;非空;非空;非空;(2 2)E E是一个不与是一个不与是一个不与是一个不与VV中顶点相交的边集合;中顶点相交的边集合;中顶点相交的边集合;中顶点相
11、交的边集合;(3 3)是关联函数。是关联函数。是关联函数。是关联函数。V V,E E,称为图的称为图的称为图的称为图的三要素三要素三要素三要素。说明:说明:说明:说明:(1 1)V V非空,即没有顶点的图不讨论;非空,即没有顶点的图不讨论;非空,即没有顶点的图不讨论;非空,即没有顶点的图不讨论;(2 2)E E无非空条件,即允许没有边;无非空条件,即允许没有边;无非空条件,即允许没有边;无非空条件,即允许没有边;(3 3)条件()条件()条件()条件(2 2)是指点只在边的端点)是指点只在边的端点)是指点只在边的端点)是指点只在边的端点处相交;处相交;处相交;处相交;(4 4)任一条边必须与一
12、对顶点关联,)任一条边必须与一对顶点关联,)任一条边必须与一对顶点关联,)任一条边必须与一对顶点关联,反之不然。反之不然。反之不然。反之不然。v1v1v3v3v2v2v4v4v5v5v1v1v3v3v2v2v4v4v5v5有向图有向图v1v1v3v3v2v2v4v4v6v6v5v5e1e1e3e3e5e5e6e6e4e4e8e8e7e7e2e2例例10-5V=(v1,v2,.v6)E=(e1,e2,.e8)(e1)=(v1,v2)(e2)=(v1,v2)(e7)=(v3,v5)(e8)=(v4,v4)次(度)次(度):与顶点关联的边数。:与顶点关联的边数。简单图简单图:没有环和重边的图。:没有
13、环和重边的图。悬挂点悬挂点:次为:次为1的点。的点。悬挂边悬挂边:次为:次为1的边。的边。孤立点孤立点:次为:次为0的点。的点。(e8)=(v4,v4),称为自回路称为自回路(环环);v6是孤立点,是孤立点,v5为悬挂点,为悬挂点,e7为悬挂边,为悬挂边,顶点顶点v3的次为的次为4,顶点,顶点v2的次为的次为3。定理定理1:在一个图中,所有顶点次的和:在一个图中,所有顶点次的和等于边的两倍。等于边的两倍。定理定理8-1:在一个图中,所有顶点次:在一个图中,所有顶点次的和等于边的两倍。的和等于边的两倍。定理定理2:在任意一个图中,奇顶点的:在任意一个图中,奇顶点的个数必为偶数。个数必为偶数。证明
14、证明:设设V1和和V2分别为分别为G中奇点和偶点的集合中奇点和偶点的集合,定理定理8-1:在一个图中,所有:在一个图中,所有顶点次的和等于边的两倍。顶点次的和等于边的两倍。定理定理8-2:在任意一个图中,:在任意一个图中,奇顶点的个数必为偶数。奇顶点的个数必为偶数。注意:注意:一个图的形状并不唯一个图的形状并不唯一。但它的三要素是不能变一。但它的三要素是不能变的。的。注意:注意:注意:注意:一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。例如:这两个图均为例如
15、:这两个图均为例如:这两个图均为例如:这两个图均为KK4 4v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v v3 3v v4 4定义定义:设设G=(V,E,)和和G1=(V1,E1,1)。)。如果如果V1 V,E1 E则称则称G1为为G的子图;的子图;如果如果G1=(V1,E1,1)是是G=(V,E,)子图,并且子图,并且V1=V,则称则称G1为为G的生成子图;的生成子图;如果如果V1 V,E1是是E中所有端点属中所有端点属于于V1的边组成的集合,的边组成的集合,则称则称G1是是G的关于的关于V1的导出子图;的导出子图;如果如果G1=(V1,E1,1)是是G=(V,
16、E,)子图,并且子图,并且V1=V,则称则称G1为为G的的生成(支撑)子图。生成(支撑)子图。v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2v1v1v5v5v4v4v2v2e1e1e5e5e3e3(a a)的子图的子图的子图的子图v1v1v5v5v4v4v2v2v3v3e8e8e6e6e5e5e2e2(a a)的生的生的生的生成子图成子图成子图成子图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2v1v1v5v5v4v4v2v2e1e1e8e8e7e7e6e6e5e5e4e4e3e
17、3(a a)的导的导的导的导出子图出子图出子图出子图定义(简单图)定义(简单图)如果图中任意如果图中任意两个顶点之间至多有一条边,两个顶点之间至多有一条边,则称为简单图,否则称为多重则称为简单图,否则称为多重图。即图。即:无环、无重边的图。无环、无重边的图。定义(简单图)定义(简单图)如果图中任意如果图中任意两个顶点之间至多有一条边,两个顶点之间至多有一条边,则称为简单图,否则称为多重则称为简单图,否则称为多重图。图。定义(有向图)定义(有向图)如果图中每一如果图中每一条边都规定了方向,则称为有条边都规定了方向,则称为有向图。向图。有向图去掉箭头得到的图称有向图去掉箭头得到的图称为基础图。为基
18、础图。定义(链)定义(链)如果图中的某些点、如果图中的某些点、边可以排列成点和边的交错序边可以排列成点和边的交错序列,则称此为一条链。列,则称此为一条链。定义(链)定义(链)如果图中的某些点、如果图中的某些点、边可以排列成点和边的交错序边可以排列成点和边的交错序列,则称此为一条链。列,则称此为一条链。定义(圈)定义(圈)如一条链中起点和如一条链中起点和终点重合,则称此为一条圈。终点重合,则称此为一条圈。v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e
19、6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图链(路)链(路)初等链(点
20、不同)初等链(点不同)简单链(边不同)简单链(边不同)v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3圈(回路)圈(回路)圈(回路)圈(回路)连通图:图中任何两个点之间必有一条链。连通图:图中任何两个点之间必有一条链。否则,称为不连通图。否则,称为不连通图。v1v1v5v5v4v4v2v2v3v3e1e1e7e7e6e6e5e5e4e4e3e3e2e2v6v6v7v7v8v8二、图的矩阵表
21、示二、图的矩阵表示一个图非常直观,但是不一个图非常直观,但是不容易计算,特别不容易在计算容易计算,特别不容易在计算机上进行计算,一个有效的解机上进行计算,一个有效的解决办法是将图表示成矩阵形式,决办法是将图表示成矩阵形式,通常采用的矩阵是邻接矩阵、通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关边长邻接矩阵、弧长矩阵和关联矩阵。联矩阵。1邻接矩阵邻接矩阵邻接矩阵邻接矩阵A表示图表示图G的顶点之的顶点之间的邻接关系,它是一个间的邻接关系,它是一个nn的矩的矩阵,如果两个顶点之间有边相联时,阵,如果两个顶点之间有边相联时,记为记为1,否则为,否则为0。v1v1v2v2v3v3v4v4v1v2v
22、3v4v10111v21110v31101v41010无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。v1v1v2v2v3v3v4v4v1v1v5v5v4v4v3v3v2v2也可以也可以也可以也可以对有向对有向对有向对有向图图图图v1v2v3v4v5v100011v210010v301100v401101v510010二、边长邻接矩阵二、边长邻接矩阵在图的各边上一个数量指标,在图的各边上一个数量指标,具体表示这条边的权(距离,单价,具体表示这条边的权(距离,单价,通过能力等)通过能力等)赋权图或网络。赋权图或网络。无向网络;有向网
23、络;混合网络;无向网络;有向网络;混合网络;边权网络;点权网络;边权网络;点权网络;以边长代替邻接矩阵中的元素得到以边长代替邻接矩阵中的元素得到边长邻接矩阵。边长邻接矩阵。v1v1v2v2v3v3v4v42 25 56 64 43 34 4v1v2v3v4v10256v2243 v35304v46 40其中其中 表示两点之间不能连接表示两点之间不能连接。3弧长矩阵弧长矩阵对有向图的弧可以用弧长对有向图的弧可以用弧长矩阵来表示。其中矩阵来表示。其中 表示两点表示两点之间没有之间没有弧弧连接连接。v1v1v5v5v4v4v3v3v2v21 14 42 23 32 22 26 61 12 2v1v2
24、v3v4v5v101 2v2 02 4v3 201 v4 3206v5 04关联矩阵关联矩阵关联矩阵关联矩阵B揭示了图揭示了图G的顶点和的顶点和边之间的关联关系,它是一个边之间的关联关系,它是一个nxm矩阵。矩阵。1(vi,vk)=ejBij=-1(vk,vi)=ej0其他其他v1v1v2v2v4v4v3v3e1e1e2e2e4e4e3e3e7e7e5e5e6e6e1e2e3e4e5e6e7v11-110000v200-1-1-100v3010101-1v4-10001-11对无向图不存在对无向图不存在-1元素元素。10-2 10-2 最优树问题(或最小树)最优树问题(或最小树)树是一类极其简
25、单而很有用的图。树是一类极其简单而很有用的图。定义(链)定义(链)如果图中的某些点、边可如果图中的某些点、边可以排列成点和边的交错序列,则称此以排列成点和边的交错序列,则称此为一条链。为一条链。定义(链)定义(链)如果图中的某些点、边如果图中的某些点、边可以排列成点和边的交错序列,则可以排列成点和边的交错序列,则称此为一条链。称此为一条链。定义(圈)定义(圈)如一条链中起点和终点如一条链中起点和终点重合,则称此为一条圈。重合,则称此为一条圈。定义(连通图)定义(连通图)如果图中的任意如果图中的任意两点之间至少存在一条通路,则两点之间至少存在一条通路,则称图为连通图,否则为不连通图。称图为连通图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 -图与网络1qh 网络 qh
限制150内