运筹学课件第一节图与网络的基本知识.ppt

《运筹学课件第一节图与网络的基本知识.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第一节图与网络的基本知识.ppt（56页珍藏版）》请在三一办公上搜索。

1、图的基本概念 图论是专门研究图的理论的一门数学分 支，主要研究点和边之间的几何关系。,复习第一节 图与网络的基本知识,图的基本概念,G=（V，E）,子图,矩阵表示,含元素的个数,点的次,边,图,点边关系,简单图,多重图,连通图,树,生成子图,第二节 树,主要内容 一、树的概念以及性质 二、图的生成树：深探法、广探法和破圈法 三、最小生成树：避圈法和破圈法 四、根树及其应用,树是一类极其简单而很有用的图。多级辐射制的电信网络、家谱、分类学、管理组织结构等都是典型的树图。,一、树的概念以及性质,树实际上是连通图，但没有圈。由所有节点(n)和相应的边(n-1)组成。,定义14（树）:一个无圈的连通无

2、向图称为树。树中次为1的点为树叶；次大于1的点为分枝点。,b,f,e,d,v1,v2,v3,v4,v5,d(v1)=1;v1树叶,d(v2)=1;v2树叶,d(v5)=1;v5树叶,d(v4)=4;v4分枝点,d(v3)=1;v3树叶,例：判断下列图形是否为树,树,树,树,树,树,树,树的性质：1、在图中任意两点之间必有一条而且只有一条链。2、在图中划去一条边，则图不连通。3、在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4、图中边数有m=n-1（n为顶点数）,定理6:图T=(V,E),点数=n;边数=m；下列关于树的说法等价。,（1）T是一棵树；,（2）T无圈，且m=n-1；,（

3、3）T连通，且m=n-1；,（4）T无圈，但任加一新边得到唯一一个圈；,（5）T连通，但任舍去一边就不连通；,（6）T任意两点，有唯一链相连。,b,c,f,e,d,h,g,a,b,c,h,图3,图4,图5,图6,图7,图8,a,二、图的生成树,定义15如果图T是G的一个生成子图，而且T又是一棵树，则称图T为一棵生成树（支撑树）。,子图定义：设G=（V，E）和G1=（V1，E1）。如果V1 V，E1 E，且E1边仅与V1中的顶点相关联，则称G1为G的子图；生成子图定义：如果G1=（V1，E1）是G=（V，E）子图，并且V1=V，则称G1为G的生成子图。,生成树与子图、生成子图的关系,一个子图与生

4、成树的区别是：子图与原图相比少边又少点，生成树与原图相比少边不少点。一个生成子图与生成树的区别是：生成子图可能含有圈，生成树无圈。图中属于生成树的边为树枝，不在生成树中的边为弦。,子图,练习1：找出图G的子图，生成子图，生成树,图1,e8,图G,生成子图,e1,e8,e6,e4,e3,e2,v5,v3,v4,v2,v1,图2,图G,生成子图；生成树；树枝e2,e3,e5,e6;弦e1,e4,e7,e8,e5,e2,e6,图3,图G,e3,e1,e8,e7,e6,e5,e4,e3,e2,v5,v3,v4,v2,v1,v3,v2,v1,v4,v5,定理7图G有生成树的充分必要条件为图G是连通图。生

5、成树的求解方法：（1）深探法步骤：a.在点集V中任取一点v,给v标号0；b.如果某点u已经得到标号i,检查一端点为u的各边，另一端是否已经标号。如果有（u,w）边的w点未标号，则给w以标号i+1,记下边（u,w）。令w代替u,继续重复。如果有（u,w）边的w已经标号，则退到标号i-1的r点,令r代替u,继续重复。,0,1,2,3,4,5,6,7,8,9,10,11,12,13,u已经得到标号,检查一端点为u的各边，另一端w是否已经标号，有（u,w）边的w已经标号，则退到标号i-1的r点,令r代替u,继续重复。,r=5-1;r代替u,原则：不能成圈,原则：不能成圈,原则：不能成圈,0,1,2,3

6、,4,5,6,7,8,9,10,11,12,13,（2）广探法步骤：a.在点集V中任取一点v,给v标号0；b.令所有标号i的点集为Vi,检查Vi,VVi中的边端点是否已经标号，对所有的未标号的点均标号i+1,记下这 些边。c.对标号i+1的点继续重复步骤b，直至全部点得到标号,0,1,1,1,2,2,2,2,3,3,3,4,1,2,A,B,图的生成树不唯一,0,（3）破圈法(深探法和广探法核心是避免成圈)步骤：从图G任取一个圈,从圈中任舍弃一条边,将此圈破掉。重复以上步骤直至无圈为止。,圈1,圈2,圈3,圈4,圈5,圈6,v1,v2,v3,v4,v5,v6,v7,练习2：分别使用深探法、广探法

7、、破圈法找出下图的一个生成树,0,1,2,3,4,使用深探法找出下图的一个生成树,使用广探法找出下图的一个生成树,使用破圈法找出下图的一个生成树,圈1,圈,圈,圈,求最小树的方法有避圈法和破圈法。,三、最小生成树,定义16：在赋权图G中，一棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，称为最小生成树或最小树或最小支撑树。,最小树的应用：设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来。,例 一个乡有9个村，道路及其道路长度如图，如何拉电线才能使电线总长度最短?,1、避圈法（krusakal）步骤：每步从未选的边中选取边e,使它与已经选的边不构成圈

8、，且e是未选边中的最小权边，直到选够n-1条边。,解（1）先将图中边按照大小顺序由小到大排列(v0,v2)=1,(v3,v2)=1,(v3,v4)=1,(v1,v8)=1；(v0,v1)=2,(v0,v6)=2,(v5,v6)=2(v0,v3)=3,(v6,v7)=3;(v0,v4)=4,(v0,v5)=4,(v0,v8)=4,(v1,v2)=4,(v0,v7)=5,(v7,v8)=5,(v4,v5)=5,定理8:用避圈法(kruskal)算法得到的子图为一棵最小树,V1,V0,V8,V2,V3,V4,V5,V6,V7,1,3,2,1,1,2,1,2,使用电话线最小长度L=1+1+1+1+2+

9、2+2+3=13,2、破圈法步骤：(1)从图G中任选一棵树T1;(2)加上一条弦e1,T1+e1中立即生成一个圈。去掉此圈中的最大权边，得到新树T2,以T2代替T1，继续重复检查剩余的弦，直到全部弦检查完毕。,定理9：图G的生成树T为最小树，当且仅当对任一弦e来讲，e是T+e中与之对应的圈ue中的最大权边。,例：先求出一棵树T1，加以弦（v1,v2），得到圈v1v2v0v1,去掉最大权边（v1,v2）;再加上弦（v2,v3），得到圈v2v3v0v2,去掉最大权边（v0,v3）,全部弦。,2,1,3,4,1,4,2,5,4,4,1,5,2,3,5,1,V1,V0,V7,V6,V8,V2,V3,V

10、4,V5,使用电话线最小长度L=1+1+1+1+2+2+2+3=13,另一种破圈法：找圈，擦除最大边以破圈。,赋权图G,生成最小树T,1,2,3,1,2,1,1,2,圈1,圈2,圈3,圈4,圈5,圈6,圈7,圈8,使用电话线最小长度L=1+1+1+1+2+2+2+3=13,V1,V6,V3,V4,V5,V2,V7,4,3,2,3,2,4,5,1,7,2,6,7,4,练习3：破圈法求下图的最小树,最小树的权=3+3+2+2+1+2=13,9,3,17,4,1,23,练习4：避圈法求下图的最小树,最小树的权=1+4+9+3+17+23=57,v2,v3,v4,v5,v6,v7,v1,根：根树入次=

11、0的点；叶:根树出次=0的点；其他的顶点为分枝点。层次：由根到某一顶点的道路长度（假设每边的长度为1），称为点的层次。,四、根树及其应用,1、根树对有向图而言,根树在计算机科学、决策论有重要应用,定义17：如果一个有向图在不考虑边的方向时是一棵树，此有向图为有向树。,定义18：有向树T,恰好有一个结点入次=0，其余各点入次=1，树T为根树（外向树）。,V1:根,V1,V4,V9,V8,V7,V6,V5,V2,V10,V3,例,V5,V6,V4,V7,V9,V10：叶,V1,V2.V3,V8：分枝点,V2,V3,V4的层次：1V5,V6,V7,V8,V9的层次：2V10层次：3,v1入次=0,其

12、它点入次=1,T,根树,v5,v6出次=0,v4出次=0,v7,v9出次=0,v10出次=0,根树应用:系统的传递关系;指挥系统的上下级关系;计算机科学的应用,有向树,定义19：在根树中，如果每个顶点的出次等于m或零，称此树为完全m叉树。如每个顶点的出次小于或等于m称此树为m叉树。,当m=2时，为完全二叉树、二叉树。,完全三叉树,四叉树,出次=3,出次=3,出次=0,出次=3,出次=2,出次=4,出次=1,出次=0,算法步骤：（1）将s个叶子按照权大小排序。（2）将二个具有最小权的叶子合并成一个分枝点，其权p1+p2;将新得到的分枝点作为一个叶子。令s=s-1,如果s=1，停止，否则转（1）。

13、,实际问题中经常讨论叶子上带权的二叉树。有s个叶子的二叉树T各个叶子的权分别为pi,根到叶子的层次为Li(i=1,2,s),这样叶子的二叉树的总权数m(T)=满足总权最小的二叉树为最优二叉树或霍夫曼树。,例：S=6,其权分别为4，3，3，2，2，1，求最优二叉树,1,2,2,3,4,3,3,5,6,9,15,总权为m（T）=42+1 4+24+2 3+3 2+3 2=38绿色为叶子;黑色为层次。,例:使用计算机进行图书分类。现有5类图书共100万册，其中有A类50万册，有B类20万册，有C类5万册，有D类10万册，有E类15万册。问如何安排分拣过程，可使总的运算（比较）次数最小？,2、最优二叉

14、树的应用,解：先构造一棵具有5个叶子的最优二叉树，令其叶子的权分别为50，20，5，10，15，然后构造最优二叉树。,5,10,15,20,50,15,30,50,C D E B A,100,A？,B？,A,N,Y,E？,B,N,Y,D？,E,N,Y,D,N,Y,C,m（T）=54+10 4+15 3+20 2+50 1=195,思考题:如何将实际应用与最小生成树的算法联系起来？,小结：1、树的概念以及性质。2、图的生成树：深探法、广探法和破圈法。3、最小生成树：避圈法和破圈法。4、根树及其应用。,证明：(1)T是一棵树,由于T是一棵树，根据定义，T是连通且无圈。现在需要证明边数m=n-1。用

15、归纳法：当n=2，由于T是一棵树，所以两点之间只有1条边，满足m=n-1；假设当n=k-1时命题成立，有k-1个顶点，有k-2条边。,b,f,e,d,u,v,T,(2)T无圈，且m=n-1,T1,e,u,证明：(1)T是一棵树,当n=k时，T是连通且无圈，k个顶点至少有1个点次为1.设点u，为悬挂点，边e=(u,v);从T中去掉边e和点u不会影响T的连通，得到T1:T1为树只有k-1个顶点，有k-2条边，再把e=(u,v)点u加上去，可知当T有k 个顶点时有k-1条边。,b,f,e,d,u,v,T,(2)T无圈，且m=n-1,T1,e,u,证明：（2）T无圈，且m=n-1,（3）T连通，且m=

16、n-1,只需要T证明是连通的。反证法：假设T不是连通的，可以分为L个连通子图(L2)，设第i个子图有ni个顶点，因为第i个连通子图是树，所以有ni-1条边，L个子图共有边数为：与已知矛盾。所以T是连通图。,先证明T无圈。假设T中有圈，设为C,可以去掉C中的一条边，并不影响T的连通性。如果剩余图中仍有圈，可继续去掉一条边，像这样去掉p条边(p1)后得到一个没有圈的连通图T1，T1显然有n-1-p（5-1-2=2）条边。但T1为树，顶点个数又与T相同为n个，所以T1应该有n-1（5-1=4）条边，矛盾，所以T中无圈。由于T连通且无圈,两点之间必有一条唯一的链，否则会出现圈，所以，T+(u,v)出现

17、唯一的一个圈。,证明:（3）T连通，且m=n-1,（4）T无圈，但任加一新边得到唯一一个圈,T,圈c,T1,证明：（4）T无圈，但任加一新边得到唯一一个圈,（5）T连通，但任舍去一边就不连通,先证明T连通。如果T不连通，由定义至少存在2点u,w之间无路可通，则加上一边(u,w)也不会形成圈，与已知T无圈矛盾。再证明每舍去一边便不连通。如果T中有一边(u,v),舍去一边(u,v)后图T-(u,v)仍然连通，那么T1=T-(u,v)由于没有圈是一个树，但T1加一边后(u,v)就是T仍无圈，与（4）中的树每加一新边必出现唯一圈矛盾。,b,f,e,d,T,T1,u,w,v,证明（5）T连通，但任舍去一边就不连通,（6）T任意两点，有唯一链相连,根据T连通，得到T中任意两点之间至少一条链相连；根据条件（5）：T连通，但任舍去一边就不连通，说明T任意两点，有唯一链相连。,证明：（6）T任意两点，有唯一链相连,（1）T是一棵树,树的定义：无圈且连通，得到证明。,