资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九章 图与网络,引言,图论是专门研究图的理论的一门数学分支,属于离散数学范畴,与运筹学有交叉,它有200多年历史,大体可划分为,三个阶段,:,第一阶段,是从十八世纪中叶到十九世纪中叶,处于萌芽阶段,多数问题围游戏而产生,最有代表性的工作是所谓的Euler七桥问题,即一笔画问题。,第二阶段,是从十九世纪中叶到二十世纪中叶,这时,图论问题大量出现,如Hamilton问题,地图染色的四色问题以及可平面性问题等,这时,也出现用图解决实际问题,如Cayley把树应用于化学领域,Kirchhoff用树去研究电网络等,.,第三阶段,是二十世纪中叶以后,由生产管理、军事、交通、运输、计算机网络等方面提出实际问题,以及大型计算机使大规模问题的求解成为可能,特别是以Ford和Fulkerson建立的网络流理论,与线性规划、动态规划等优化理论和方法相互渗透,促进了图论对实际问题的应用。,A,B,C,D,最后,数学家Euler在1736年巧妙地给出了这个问题的答案,并因此奠定了图论的基础,Euler把A、B、C、D四块陆地分别收缩成四个顶点,把桥表示成连接对应顶点之间的边,问题转化为从任意一点出发,能不能经过各边一次且仅一次,最后返回该点。这就是著名的,Euler,问题。,A,C,B,D,1,2,3,7,6,4,5,假定第一次就座方案是,(1,2,3,4,5,6,7,1),那么第二次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,例9-3:,哈密顿(Hamilton)回路是十九世纪英国数学家哈密顿提出,给出一个正12面体图形,共有20个顶点表示20个城市,要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次,最后回到原处的周游世界线路(并不要求经过每条边)。,例9-4:,一个班级的学生共计选修A、B、C、D、E、F六门课程,其中一部分人同时选修D、C、A,一部分人同时选修B、C、F,一部分人同时选修B、E,还有一部分人同时选修A、B,期终考试要求每天考一门课,六天内考完,为了减轻学生负担,要求每人都不会连续参加考试,试设计一个考试日程表。,A,F,E,D,C,B,A,F,E,D,C,B,A,F,E,D,C,B,定义,:(图),设G=(V,E,,),其中:V=(v,1,,v,2,,.v,m,),是m个顶点集合;,E=(e,1,,e,2,,.e,n,),是n条边集合。,是描述边与顶点之间关系的函数,称G=(V,E,,)为 一个图,如果它满足:,(1)V非空;,(2)E是一个不与V 中顶点相交的边集合;,(3),是关联函数。,V,E,,称为图的,三要素,。,v1,v3,v2,v4,v6,v5,e1,e3,e5,e6,e4,e8,e7,e2,例9-5,V=(v,1,,v,2,,.v,6,),E=(e,1,,e,2,,.e,8,),(e,1,)=(v,1,,v,2,),(e,2,)=(v,1,,v,2,),(e,7,)=(v,3,,v,5,),(e,8,)=(v,4,,v,4,),(e,8,)=(v,4,,v,4,),称为自回路(环);,v,6,是孤立点,v,5,为悬挂点,e,7,为悬挂边,顶点v,3,的次为4,顶点v,2,的次为3。,定理9-1:在一个图中,所有顶点次的和等于边的两倍。,定理9-2:在任意一个图中,奇顶点的个数必为偶数。,注意:一个图的形状并不唯一。但它的三要素是不能变的。,定义,:,设G=(V,E,,)和,G,1,=(V,1,,E,1,,,1,)。,如果,V,1,V,E,1,E则称G,1,为G的子图;,如果G,1,=(V,1,,E,1,,,1,)是,G=(V,E,,),子图,并且V,1,=,V,则称G,1,为G的生成子图;,如果,V,1,V,E,1,是E中所有端点属于V,1,的边组成的集合,,则称G,1,是G的关于V,1,的导出子图;,如果G,1,=(V,1,,E,1,,,1,)是,G=(V,E,,),子图,并且V,1,=,V,则称G,1,为G的生成子图。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3,(a)的子图,v1,v5,v4,v2,v3,e8,e6,e5,e2,(a)的生成子图,v1,v5,v2,e1,e6,e5,(a)的导出子图,定义(简单图)如果图中任意两个顶点之间至多有一条边,则称为简单图,否则称为多重图。,定义(有向图)如果图中每一条边都规定了方向,则称为有向图。,定义(链)如果图中的某些点、边可以排列成点和边的交错序列,则称此为一条链。,定义(圈)如一条链中起点和终点重合,则称此为一条圈。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,圈,二、图的矩阵表示,一个图非常直观,但是不容易计算,特别不容易在计算机上进行计算,一个有效的解决办法是将图表示成矩阵形式,通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。,1 邻接矩阵,邻接矩阵A表示图G的顶点之间的邻接关系,它是一个nxn的矩阵,如果两个顶点之间有边相联时,记为1,否则为0。,v1,v2,v3,v4,2,5,6,4,3,4,v1 v2 v3 v4,v1 0 1 1 1,v2 1 1 1 0,v3 1 1 0 1,v4 1 0 1 0,无向图的邻接矩阵是对称矩阵。,v1,v5,v4,v3,v2,也可以对有向图,v1 v2 v3 v4 v5,v1 0 0 0 1 1,v2 1 0 0 1 0,v3 0 1 1 0 0,v4 0 1 1 0 1,v5 1 0 0 1 0,二、边长邻接矩阵,在图的各边上一个数量指标,具体表示这条边的权(距离,单价,通过能力等)赋权图或网络。,无向网络;有向网络;混合网络;边权网络;点权网络;,以边长代替邻接矩阵中的元素得到边长邻接矩阵。,v1,v2,v3,v4,2,5,6,4,3,4,v1 v2 v3 v4,v1 0 2 5 6,v2 2 4 3,v3 5 3 0 4,v4 6,4 0,其中,表示两点之间不能连接,。,3 弧长矩阵,对有向图的弧可以用弧长矩阵来表示。其中,表示两点之间没有,弧,连接,。,v1,v5,v4,v3,v2,1,4,2,3,2,2,6,1,2,v1 v2 v3 v4 v5,v1 0 1,2,v2,0 2,4,v3,2 0 1,v4,3 2 0 6,v5,0,4,关联矩阵,关联矩阵B揭示了图G的顶点和边之间的关联关系,它是一个nxm矩阵。,1 (v,i,,v,k,)=e,j,B,ij,=-1 (v,k,,v,i,)=e,j,0 其他,v1,v2,v4,v3,e1,e2,e4,e3,e7,e5,e6,e1 e2 e3 e4 e5 e6 e7,v1 1 -1 1 0 0 0 0,v2 0 0 -1,-1 -1 0 0,v3 0 1 0 1 0 1 -1,v4 -1,0,0 0 1 -1 1,对无向图不存在-1 元素。,9-2 最优树问题,树是一类极其简单而很有用的图。,定义(链),如果图中的某些点、边可以排列成点和边的交错序列,则称此为一条链。,定义(圈),如一条链中起点和终点重合,则称此为一条圈。,定义(连通图),如果图中的任意两点之间至少存在一条通路,则称图为连通图,否则为不连通图。,定义(树),一个无圈的连通图称为树。如果一个无圈的图中每一个分支都是树,则称图为森林。,树的性质:,1 在图中任意两点之间必有一条而且只有一条通路。,2 在图中划去一条边,则图不连通。,3 在图中不相邻的两个顶点之间加一条边,可得一个且仅得一个圈。,4 图中边数有n,e,=p-1(p为顶点数),a,b,c,f,e,d,h,g,例9-6,b,f,e,d,b,f,d,g,b,c,e,d,a,b,c,h,a,f,d,g,定义(生成树),如果图T是G的一个生成子图,而且T又是一棵树,则称图T为一棵生成树。对于分离图,则称为生成森林。,一个子图与生成树的区别是:子图与原图相比少弧又少点,生成树与原图相比少弧不少点。,定理,图 G有生成树的充分必要条件为图是连通图。,定义(最优树),在赋权图G中,一棵生成树所有树柱上权的和,称为生成树的权。具有最小权的生成树,称为最优树(或最小树)。,求最小树的方法有,破圈法,和,避圈法,。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,例9-7,破圈法,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总造价=1+4+9+3+17+23=57,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,避圈法,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,总造价=1+4+9+3+17+23=57,其他树搜索树,一、,-方法(是人工智能中常用方法),例9-8:,有n根火柴,甲乙两个依次可以从中任意取走1根或2根,但不能不取,取走最后一根火柴者为胜方,试讨论取胜策略。为了便于理解,不妨假设n=7。,7,5,4,4,3,3,1,2,2,2,1,1,2,6,5,1,2,2,2,3,4,1,2,3,3,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,-1,+1,+1,+1,-1,-1,-1,-1,-1,-1,-1,-1,-1,在树形图中,圆圈中数字7表示轮到甲方取时还有7根,方框中数字6表示表示轮到乙方取时还有6根,依次类推。显然,一旦最后出现方框(1或2)状态时乙方胜。反之,若最后出现圆圈(1或2)状态时甲方胜。,若甲方胜时得分+1,乙方胜时甲方得分-1,无凝轮到甲方取时一定选择能使他进入得分+1状态。同理轮到乙方取时一定选择能使甲方进入得分-1状态。,这样从树叶开始逐层向上,就可以算术出甲方胜负情况。,不难看出,n=1或n=2时,先取者为胜,n=3时,先取者为败。,如果n=3k(k正整数),假定先取者拿走a根(a=1或2),则后者只要取走b 根,(满足a+b=3),使余下火柴为3(k-1)根,那么先取者必败。如果n不等于3k,则先取者取a根,使n-a=3k,那么先取者必胜。,二、DFS和BFS法,DFS(Depth First Search),深度优先法或深探法。,BFS(Breadth First Search),广度优先法或广探法。,例9-9:,一个人带领一条狗、一只羊和一筐菜过河,河中有一条小船,只能乘一个人和一样东西,而如果人不在场时,狗要咬羊,羊要吃菜,设想一种过河方案。,解:,用m、a、b、c表示人、狗、羊和菜。用广探法确定(奇数次)过河方案。(二种过河方案),m,a,b,c a c,m,a c,m b,b,a,m,a,b,m,b,c,c,c,m,b,c,m a,b a,b,m,b,m,a,c,a c,m,a,b,c,
展开阅读全文