运筹学 第一节 图与网络的基本知识

运筹学课件第一节图与网络的基本知识1第一页，共五十六页，2022年，8月28日图的基本概念G=（V，E）子图矩阵表示含元素的个数点的次边图点边关系简单图多重图连通图树生成子图2第二页，共五十六页，2022年，8月28日第二节树

主要内容

一、树的概念以及性质二、图的生成树：深探法、广探法和破圈法三、最小生成树：避圈法和破圈法四、根树及其应用3第三页，共五十六页，2022年，8月28日树是一类极其简单而很有用的图。多级辐射制的电信网络、家谱、分类学、管理组织结构等都是典型的树图。某企业的组织结构图总经理生产经理人力经理销售经理车间主任销售代表招聘人员一、树的概念以及性质ABCDEFN乒乓球单打比赛抽签后，用图表示相遇情况v1v2w1v3w2V4第四页，共五十六页，2022年，8月28日树实际上是连通图，但没有圈。由所有节点(n)和相应的边(n-1)组成。定义14（树）:一个无圈的连通无向图称为树。树中次为1的点为树叶；次大于1的点为分枝点。bfedv1v2v3v4v5d(v1)=1;v1树叶d(v2)=1;v2树叶d(v5)=1;v5树叶d(v4)=4;v4分枝点d(v3)=1;v3树叶5第五页，共五十六页，2022年，8月28日例：判断下列图形是否为树图1v1v2e1树图2v1v2v3e1e2e36第六页，共五十六页，2022年，8月28日v2abcfedhg图3v1v3v4v5图4bfdgv1v2v3v5v4树7第七页，共五十六页，2022年，8月28日abch图5v1v2v3v4v5bced图6v1v2v3v4v5树树8第八页，共五十六页，2022年，8月28日v4v3afdg图7v1v2v5v3bfed图8v1v2v4v5树树9第九页，共五十六页，2022年，8月28日树的性质：1、在图中任意两点之间必有一条而且只有一条链。2、

在图中划去一条边，则图不连通。3、

在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4、图中边数有m=n-1（n为顶点数）10第十页，共五十六页，2022年，8月28日定理6:图T=(V,E),点数=n;边数=m；下列关于树的说法等价。（1）T是一棵树；（2）T无圈，且m=n-1；（3）T连通，且m=n-1；（4）T无圈，但任加一新边得到唯一一个圈；（5）T连通，但任舍去一边就不连通；（6）T任意两点，有唯一链相连。11第十一页，共五十六页，2022年，8月28日bcfedhgbfedbfdgbcedabchafdg图3图4图5图6图7图8a12第十二页，共五十六页，2022年，8月28日二、图的生成树定义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的生成子图。13第十三页，共五十六页，2022年，8月28日生成树与子图、生成子图的关系

一个子图与生成树的区别是：子图与原图相比少边又少点，生成树与原图相比少边不少点。一个生成子图与生成树的区别是：生成子图可能含有圈，生成树无圈。图中属于生成树的边为树枝，不在生成树中的边为弦。14第十四页，共五十六页，2022年，8月28日子图练习1：找出图G的子图，生成子图，生成树图1e1e8e7e6e5e4e3e2v5v3v4v2v1e8e1e7e6e5e4e3v5v4v2v1图G15第十五页，共五十六页，2022年，8月28日生成子图e1e8e7e6e5e4e3e2v5v3v4v2v1e1e8e6e4e3e2v5v3v4v2v1图2图G16第十六页，共五十六页，2022年，8月28日生成子图；生成树；树枝e2,e3,e5,e6;弦e1,e4,e7,e8e5e2e6图3图Ge3e1e8e7e6e5e4e3e2v5v3v4v2v1v3v2v1v4v517第十七页，共五十六页，2022年，8月28日定理7图G有生成树的充分必要条件为图G是连通图。生成树的求解方法：（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,继续重复。18第十八页，共五十六页，2022年，8月28日012345678910111213u已经得到标号,检查一端点为u的各边，另一端w是否已经标号，有（u,w）边的w已经标号，则退到标号i-1的r点,令r代替u,继续重复。r=5-1;r代替u19第十九页，共五十六页，2022年，8月28日原则：不能成圈原则：不能成圈原则：不能成圈.0.1.3.4.5.2.6.7.8.9.10.11.12.1301234567891011121320第二十页，共五十六页，2022年，8月28日（2）广探法步骤：a.在点集V中任取一点v,给v标号0；b.令所有标号i的点集为Vi,检查[Vi,V\Vi]中的边端点是否已经标号，对所有的未标号的点均标号i+1,记下这些边。c.对标号i+1的点继续重复步骤b，直至全部点得到标号21第二十一页，共五十六页，2022年，8月28日01112222333412AB22第二十二页，共五十六页，2022年，8月28日14203331112222图的生成树不唯一1111022222333423第二十三页，共五十六页，2022年，8月28日（3）破圈法(深探法和广探法核心是避免成圈)

步骤：从图G任取一个圈,从圈中任舍弃一条边,将此圈破掉。重复以上步骤直至无圈为止。圈1圈2圈3圈4圈5圈6v1v2v3v4v5v6v724第二十四页，共五十六页，2022年，8月28日练习2：分别使用深探法、广探法、破圈法找出下图的一个生成树25第二十五页，共五十六页，2022年，8月28日01234使用深探法找出下图的一个生成树26第二十六页，共五十六页，2022年，8月28日使用广探法找出下图的一个生成树０１１１２27第二十七页，共五十六页，2022年，8月28日使用破圈法找出下图的一个生成树圈1圈２圈３圈４28第二十八页，共五十六页，2022年，8月28日求最小树的方法有避圈法和破圈法。三、最小生成树定义16：在赋权图G中，一棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，称为最小生成树或最小树或最小支撑树。最小树的应用：设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来。29第二十九页，共五十六页，2022年，8月28日例一个乡有9个村，道路及其道路长度如图，如何拉电线才能使电线总长度最短?1、避圈法（krusakal）步骤：每步从未选的边中选取边e,使它与已经选的边不构成圈，且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)=5V1V0V8V2V3V4V5V6V7145325114421235430第三十页，共五十六页，2022年，8月28日V1V0V8V2V3V4V5V6V7145325114421235431第三十一页，共五十六页，2022年，8月28日定理8:用避圈法(kruskal)算法得到的子图为一棵最小树V1V0V8V2V3V4V5V6V713211212使用电话线最小长度L=1+1+1+1+2+2+2+3=1332第三十二页，共五十六页，2022年，8月28日2、破圈法步骤：(1)从图G中任选一棵树T1;(2)加上一条弦e1,T1+e1中立即生成一个圈。去掉此圈中的最大权边，得到新树T2,以T2代替T1，继续重复检查剩余的弦，直到全部弦检查完毕。定理9：图G的生成树T为最小树，当且仅当对任一弦e来讲，e是T+e中与之对应的圈ue中的最大权边。33第三十三页，共五十六页，2022年，8月28日V1V0V8V2V3V4V5V6V7145325114421235434第三十四页，共五十六页，2022年，8月28日例：先求出一棵树T1，加以弦（v1,v2），得到圈{v1v2v0v1},去掉最大权边（v1,v2

）;再加上弦（v2,v3

），得到圈{v2v3v0v2},去掉最大权边（v0,v3

）……,全部弦。2134142544152351V1V0V7V6V8V2V3V4V5使用电话线最小长度L=1+1+1+1+2+2+2+3=1335第三十五页，共五十六页，2022年，8月28日另一种破圈法：找圈，擦除最大边以破圈。赋权图G1542453134421512生成最小树T12312112圈1圈2圈3圈4圈5圈6圈7圈8使用电话线最小长度L=1+1+1+1+2+2+2+3=1336第三十六页，共五十六页，2022年，8月28日V1V6V3V4V5V2V74323245172674练习3：破圈法求下图的最小树最小树的权=3+3+2+2+1+2=1337第三十七页，共五十六页，2022年，8月28日93174123201516252836练习4：避圈法求下图的最小树最小树的权=1+4+9+3+17+23=57v2v3v4v5v6v7v138第三十八页，共五十六页，2022年，8月28日根：根树入次=0的点；叶:根树出次=0的点；其他的顶点为分枝点。层次：由根到某一顶点的道路长度（假设每边的长度为1），称为点的层次。四、根树及其应用1、根树对有向图而言,根树在计算机科学、决策论有重要应用定义17：如果一个有向图在不考虑边的方向时是一棵树，此有向图为有向树。定义18：有向树T,恰好有一个结点入次=0，其余各点入次=1，树T为根树（外向树）。39第三十九页，共五十六页，2022年，8月28日V1:根V1V4V9V8V7V6V5V2V10V3例V5,V6,V4,V7,V9,V10：叶V1,V2.V3,V8：分枝点V2,V3,V4的层次：1V5,V6,V7,V8,V9的层次：2V10层次：3v1入次=0其它点入次=1T根树v5,v6出次=0v4出次=0v7,v9出次=0v10出次=0根树应用:系统的传递关系;指挥系统的上下级关系;计算机科学的应用有向树40第四十页，共五十六页，2022年，8月28日定义19：在根树中，如果每个顶点的出次等于m或零，称此树为完全m叉树。如每个顶点的出次小于或等于m称此树为m叉树。当m=2时，为完全二叉树、二叉树。完全三叉树四叉树出次=3出次=3出次=0出次=3出次=2出次=4出次=1出次=041第四十一页，共五十六页，2022年，8月28日算法步骤：（1）将s个叶子按照权大小排序。（2）将二个具有最小权的叶子合并成一个分枝点，其权p1+p2;将新得到的分枝点作为一个叶子。令s=s-1,如果s=1，停止，否则转（1）。实际问题中经常讨论叶子上带权的二叉树。有s个叶子的二叉树T各个叶子的权分别为pi,根到叶子的层次为Li(i=1,2,…s),这样叶子的二叉树的总权数m(T)=满足总权最小的二叉树为最优二叉树或霍夫曼树。42第四十二页，共五十六页，2022年，8月28日例：S=6,其权分别为4，3，3，2，2，1，求最优二叉树12234312234335643第四十三页，共五十六页，2022年，8月28日122343356915总权为m（T）=4×2+1

×4+2×4+2×3+3×2+3×2=38绿色为叶子;黑色为层次。44第四十四页，共五十六页，2022年，8月28日例:使用计算机进行图书分类。现有5类图书共100万册，其中有A类50万册，有B类20万册，有C类5万册，有D类10万册，有E类15万册。问如何安排分拣过程，可使总的运算（比较）次数最小？2、最优二叉树的应用解：先构造一棵具有5个叶子的最优二叉树，令其叶子的权分别为50，20，5，10，15，然后构造最优二叉树。45第四十五页，共五十六页，2022年，8月28日510152050153050CDEBA100A？B？ANYE？BNYD？ENYDNYCm（T）=5×4+10×4+15×3+20×2+50×1=19546第四十六页，共五十六页，2022年，8月28日思考题:如何将实际应用与最小生成树的算法联系起来？47第四十七页，共五十六页，2022年，8月28日小结：1、树的概念以及性质。2、图的生成树：深探法、广探法和破圈法。3、最小生成树：避圈法和破圈法。4、根树及其应用。48第四十八页，共五十六页，2022年，8月28日49第四十九页，共五十六页，2022年，8月28日50第五十页，共五十六页，2022年，8月28日证明：(1)T是一棵树由于T是一棵树，根据定义，T是连通且无圈。现在需要证明边数m=n-1。用归纳法：当n=2，由于T是一棵树，所以两点之间只有1条边，满足m=n-1；假设当n=k-1时命题成立，有k-1个顶点，有k-2条边。bfeduvT(2)T无圈，且m=n-1T1eu51第五十一页，共五十六页，2022年，8月28日证明：(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条边。bfeduvT(2)T无圈，且m=n-1T1eu52第五十二页，共五十六页，2022年，8月28日证明：（2）T无圈，且m=n-1（3）T连通，且m=n-1只需要T证明是连通的。反证法：假设T不是连通的，可以分为L个连通子图(L≥2)，设第i个子图有ni个顶点，因为第i个连通子图是树，所以有ni-1条边，L个子图共有边数为：