《图论基础通风网络》PPT课件.ppt

1,课程设置目的,该门课在工程应用中的重要性,1）矿井设计2）矿井改扩建3）通风系统调整4）矿井灾害防治（瓦斯、火）,1）风量分配与调整2）风流方向判断3）通风设施合理位置的选择4）灾害烟气蔓延与避灾路线的选择,2,系统规划系统合并单一风井工作,3,授课计划,0绪论1图论基础1.1图的基本概念1.2图的矩阵表示1.3生成树选择,2矿井通风网络2.1矿井通风网络图2.2矿井通风网络内风流变化的规律2.3通风网络分析与数学模型,实验,4,授课计划,3通风机运转特性及分析3.1扇风机特性的数学描述3.2扇风机工况点求解与分析3.3用计算机进行扇风机优选,4复杂通风网络自然分风电算4.1复杂通风网络解算概述4.2回路法解算复杂风网4.3节点法与割集法解算复杂风网4.4风网自然分风算法评述4.5复杂风网自然分风电算程序实例,实验,5,授课计划,5通风网络中风流调节的计算方法5.1概述5.2独立回路法5.3道路法,6矿井通风网络优化6.1矿井通风网络优化概述6.2通风网络调节优化6.3通风中风量分配的优化6.4矿井通风系统优化设计简介,6,授课计划,7网络理论在矿井通风中的应用7.1在通风设计中的应用7.2在通风管理中的应用,8矿井火灾的通风网络解析8.1矿井火灾时期风流状态的变化规律8.2矿井火灾时的通风模拟8.3矿井火灾时风流控制8.4矿井通风模拟软件示例,实验,7,1图论基础-图的概念图的定义,顶点或节点,边或分支,图的偶对表示:图GG(V,E)节点VV(v1,v2,vm)节点集m=|V|节点数边EE(e1,e2,em)边集n=|E|边数,1）图的定义指某类具体事物和这些事物间联系的抽象描述。,1.1图的基本概念,G（m，n）,8,1图论基础-图的概念图的定义,图的拓扑关系:顶点和边间的联接关系。,有限图无限图,空图（m,n)图,根据m,n的值来确定名称,有向图无向图混合图,有序，含有有向边,无序,既有有向边，又有无向边,9,1图论基础-图的概念图的定义,图的几何表示图的图解,图G1点集：V（G1）=V(v1,v2,v5)图G1边集：E（G1）=E(e1,e2,e7)图G1为无序图，各边的联接可表示为e1=，e7=图G2为有序图，各边的联接可表示为e1=(v2,v1)，e6=(v1,v4)圆括号表示有序偶对，尖括号表示无序偶对。,G1=（5，7）,G2=（4，6）,G3=（6，9）,10,1图论基础-图的概念图的定义,关联与邻接:邻接点与邻接边点、边关联,关联与邻接的区别,v1与e1关联,v5与v6邻接,e2与e3邻接,11,1图论基础-图的概念图的定义,平行边（重边）,圈,多重图,重边数量叫重数=2,始末点重合的分支。,阶,节点个数。,完全图,每一对不同节点间均有一条边相连,m阶完全图有多少条边？,=m(m-1)/2,e10,简单图,12,1图论基础-图的概念图的同构,2）图的同构,表示节点和边的关联关系，对其它无限制。,GG,应用：根据需要将通风系统图转变成通风网络图。,（4,6）图,网络图的美化调整,13,1图论基础-图的概念子图,3）子图,真子图:,或H中至少有一个边的重数小于G中对应边的重数,且：H中边的重数不超过G中对应边的重数,生成子图:,H是包含了图G所有节点的真子图,生成子图是原图的真子图！,若,若,且,或,14,1图论基础-图的概念子图,课堂练习,根据右图1）找出3个子图；2）找出4个真子图；3）试找出2个生成子图,15,1图论基础-图的概念赋权图,4）赋权图,一个图G=（V，E）与定义在E或V上的权或权函数，称为一个网络或赋权图，亦称有权图。,在通风网络中，常用通风参数作权的指标，如风阻、风量、风压等。一般将权值注在分支旁边。,16,1图论基础-道路与回路链,闭合链和开链,1）链,对于图G的p个边e1,e2,ep,如果有p+1个顶点序列v1,v2,vp+1,且边ei与vi-1、vi关联（i=1,2p),则这些边构成的序列称为链。,ei,vi-1,vi,17,1图论基础-道路与回路链,简单链:,链:,闭链:,例,简单链:,基本链:,没有重复边的链,没有重复顶点的链,18,1图论基础-道路与回路路,2）路,路,道路/通路:,一条不闭合的基本链,方向一致的路,道路的权:,两节点间每条道路内各边的权之和,最长路与最短路,回路:,始点和终点重合的基本链,19,1图论基础-道路与回路路,课堂练习,根据右图1）找出经过2号点的2条路；2）找出3个回路。,20,1图论基础-道路与回路图的连通性,连通图:,非连通图:,图G中任意两节点间至少存在一条路,3）图的连通性,多个连通图组成,21,1图论基础-道路与回路图的连通性,图的秩:,m个节点,k个分离部分，则秩r=m-k连通图，k=1，则秩为不包含起点的所有节点数,单向连通图:,强连通图:,vi,vj,vi,vj,任意两个节点间,3）图的连通性,22,1图论基础-道路与回路欧拉公式,4）欧拉公式,重点,平面图:,把图G画在平面上，各边为简单曲线，除节点外任意两边均不相交。,23,1图论基础-道路与回路欧拉公式,4）欧拉公式,网孔f:,在自然网眼中，网眼内部既不含节点，也不含边,欧拉公式:,内部回路数C:,自然网眼:,边围成的区域,f+m-n=2,=1?,C=n-m+1,联系区别,24,1图论基础-树树的概念,不含回路的连通图。,悬挂点,仅有一条分支与其相关联的节点,割边,去掉后能使图分成两部分的边,割点,去掉与其关联的边后能使图分成两部分的点,树枝,割点与悬挂点有什么关系,1)树T,25,1图论基础-树生成树和余树,2)生成树和余树,T是图G的一个生成子图，且是一棵树。,包含所有节点；不唯一,生成树,26,生成树:,包含图G全部节点的树。,1图论基础-树生成树和余树,27,1图论基础-树生成树和余树,余树,去掉生成树T后，剩下的边构成的子图余树中即可含有回路，也可不连通,余树弦数：,余树中含的边,余树弦：,n-m+1,与欧拉公式有何联系？,28,1图论基础-树生成树和余树,生成树T,29,1图论基础-树生成树和余树,特别提醒,任何联通图的边数等于其余树弦数和树枝数之和,图的生成树连通但不含回路,余树既可含回路，也可不连通,任何图的边数等于其余树弦数和树枝数之和,30,1图论基础-树生成树和余树,特别提醒,生成树与余树之间的区别,节点数方面,回路方面,连通性方面,31,1图论基础-树基本回路,3）基本回路,由一条余树弦和T的树枝构成的回路，称为图G关于生成树T的基本回路。,1)基本回路数；2)基本回路组；3)回路组非唯一性；4)基本回路也叫独立回路；5)回路的方向性,一个图的生成树不唯一基本回路组也不唯一,32,1图论基础-树基本回路,3）基本回路,1)基本回路或独立回路数；2)基本回路组；,33,1图论基础-树最大树与最小树,4）最大树与最小树,生成树的权：,一颗生成树上所有树枝权总和。,最大树Tmax,最小树Tmin,34,1图论基础-树最大树与最小树,图的最小树是（）的树。,唯一的,不唯一,权最小,图的最大树是（）的树。,思考,以上都不是,权最大,35,1图论基础-割集割集的定义,割集S是连通图G的边的集合,把S从G中移去,使图G仅成为两部分,但如少移去S中的一条边,则图G仍是连通的。,1）割集定义,1）割集为虚线相交的边的集合；2）边的最小集合；3）若分成两个以上部分，非割集割集：S1=d,e,g;S2=a,c,e,g,36,1图论基础-割集割集的定义,割点,去除该点后，图分为两个部分。,连通图中，除了割点（如3）外，与任一点相连的边的集合均构成一个割集。,37,1图论基础-割集割集的方向,2）割集方向,1）有向割集；2）割集正方向的确定；3）正向边与负向边。,以虚线面为界，可把割集内向外穿出的方向定为割集的正方向，也可把割集外向内穿入的方向定为正方向。,38,1图论基础-割集割集与生成树关系,3）割集与生成树关系,生成树：连通图G的全部节点的最小边集合；,割集：将连通图G的节点分为不相连的二个节点子集的最少边集合。,连通图G的一个割集S至少包含图G的生成树的一条树枝。,39,1图论基础-割集基本割集,4）基本割集,S1，s2，s3，s4是关于T的基本割集组。结论：基本割集组是线性无关的。,基本割集只能包含一条树枝基本割集数=树枝数,40,1图论基础-割集基本割集,41,1图论基础-割集基本割集,说明:,基本割集只能包含一条树枝基本割集数=树枝数=m-1,基本回路只能包含一条余树弦基本回路数=余树弦数=n-m+1,重点,42,1图论基础-割集基本割集,连通平面图G(m，n),独立回路数为(),秩为(),余树弦为(),n-m+1,m-1,n-m+1,重点,考考你,43,1图论基础-割集基本割集,重点,独立回路分支的正负号,基本割集分支的正负号,基本割集内，以树枝方向为准，与其同向者为正，反之为负,独立回路分支方向以余数弦分支方向为准，与其同向者为正，反之为负。,44,1图论基础-图的矩阵表示邻接矩阵,1）邻接矩阵,表示图的节点间邻接关系的矩阵,构造方阵,其中：,1.2图的矩阵表示,45,1图论基础-图的矩阵表示邻接矩阵,例,（1）每一行的1表示什么意思？（2）每一列的1表示什么意思？（3）非零数的数量与图有什么关系？,46,1图论基础-图的矩阵表示邻接矩阵,思考,（1）如何构造无向图的邻接矩阵？,47,1图论基础-图的矩阵表示邻接矩阵,思考,（2）如何构造非简单有向图的邻接矩阵？,48,1图论基础-图的矩阵表示关联矩阵,2）关联矩阵,表示图的节点和边的关联关系的矩阵。,构造方阵,其中：,（1）完全关联矩阵,49,1图论基础-图的矩阵表示关联矩阵,矩阵Be的行向量是线性相关的，矩阵的秩R=3（4-1）.,50,1图论基础-图的矩阵表示关联矩阵,（2）基本关联矩阵,在m阶连通图G的完全关联矩阵Be中,划去任一行后,所得的(m-1)n矩阵,称为图G的基本关联矩阵，简称关联矩阵，记作B。划去的对应点称为参考点。,基本关联矩阵线性独立。通常，通风网络中划去的节点为大气节点。,51,1图论基础-图的矩阵表示关联矩阵,思考,（1）写出下图的关联矩阵。,52,1图论基础-图的矩阵表示关联矩阵,思考,（2）根据下面的关联矩阵，绘制对应的网络图。,53,1图论基础-图的矩阵表示回路矩阵,3）回路矩阵,表示一个图的边与回路关系的矩阵。,（1）完全回路矩阵,imax=2n-m+1-1jmax=n,互异回路：至少有一条边不同的回路,包含图的所有互异回路的矩阵。,54,1图论基础-图的矩阵表示回路矩阵,回路个数：26-4+1-1=7,55,1图论基础-图的矩阵表示回路矩阵,若生成树为T=(2,3,6)，余树弦为（1,4,5）,56,1图论基础-图的矩阵表示回路矩阵,完全回路矩阵的特点,每一行对应一个回路；每行非零元素组成一个回路；行数：2n-m+1;各行之间并非线性独立；秩为n-m+1（独立回路数）。,独立回路矩阵能反映完全回路性质，没有必要写完全回路矩阵？,57,1图论基础-图的矩阵表示回路矩阵,互异回路与独立回路的区别,回路数方面,线性相关方面,独立回路数为n-m+1,互异回路为2n-m+1-1个,独立回路是线性独立的,互异回路则是线性相关的,58,1图论基础-图的矩阵表示回路矩阵,（2）基本回路矩阵,基本回路矩阵一般是在某个生成树的基础上提出的。,imax=n-m+1jmax=n,若生成树为T=(2,3,6)，余树弦为（1,4,5）,59,1图论基础-图的矩阵表示回路矩阵,1)基本回路矩阵的秩等于：n-m+12)余树弦在前、树枝在后分为两部分：,生成树为T=(2,3,6)，余树弦为（1,4,5）,基本回路矩阵的性质,60,1图论基础-图的矩阵表示割集矩阵,4）割集矩阵,（1）完全割集矩阵,表达图的边与割集关系的矩阵,包含图G的全部割集的矩阵,61,1图论基础-图的矩阵表示割集矩阵,62,1图论基础-图的矩阵表示割集矩阵,取生成树,余树弦,可发现,63,1图论基础-图的矩阵表示割集矩阵,（2）基本割集矩阵,同一个图，有不同的生成树，故基本割集也不相同。,列：余树在前，树枝在后；行：按树枝在矩阵内的列序排序,64,1图论基础-图的矩阵表示矩阵间关系,5）矩阵间关系(自学),生成树,余树弦,关联矩阵,65,1图论基础-图的矩阵表示矩阵间关系,生成树,余树弦,回路矩阵,66,1图论基础-图的矩阵表示矩阵间关系,生成树,余树弦,割集矩阵,67,1图论基础-图的矩阵表示矩阵间关系,关联矩阵B与回路矩阵C的关系,回路矩阵C与割集矩阵S的关系,割集矩阵S与割集矩阵的关系,68,1图论基础-生成树的选择,1.3生成树的选择,知识点生成树的选择独立回路的选择,既是本章重点又是本章难点,69,1图论基础-生成树的选择,最大树,最小树,任意树,生成树的类型,根据权值大小进行划分,70,1图论基础-生成树的选择,破圈法,加边法,收缩法,生成树的选择方法,常用,71,1图论基础-生成树的选择破圈法,1）破圈法,1）画网络图,将点、边编号，标出风向：m=4,n=62）确定图的余树弦数（即独立回路数）N:N=n-m+1=33）将分支按权（风阻）大小排序：R1、R6、R4、R2、R5、R34）从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选；5）重复4），直到移去n-m+1条余树弦，剩余的分支即组成最小风阻树Tmin,选择最小树,为什么可能是独立回路？,72,1图论基础-生成树的选择破圈法,为什么可能是独立回路？,D,A,B,C,3,6,4,2,5,1,以分支3为例：去掉分支3,3个回路被破坏,哪个是独立回路？,4,73,1图论基础-生成树的选择破圈法,注意：若被破坏的回路中，有一条以上高阻分支，应重选！,D,A,B,C,6,1,R1、R6、R4、R2、R5、R3,以分支3为例：,如果：,4,74,1图论基础-生成树的选择破圈法,破圈法选择最小树,D,A,B,C,6,4,1,高阻分支：3，5，2最小风阻树:Tmin=(1，6，4)余树弦：，独立回路（，1，6）（，-4，-6）（，1，4，6）,75,1图论基础-生成树的选择破圈法,结果检验:每加入一条余树弦，便构成一个独立回路。,D,A,B,C,6,4,1,76,1图论基础-生成树的选择破圈法,思考,V1,V2,V3,V4,V5,e1,e2,e5,e3,e4,e6,e7,用破圈法找出左图最大树。,各分支风阻大小升序为：e6，e2，e3，e1，e7，e4，e5,77,1图论基础-生成树的选择加边法,2）加边法,加边法选择最大树,D,A,B,C,R1、R6、R4、R2、R5、R3,4）重复3），将所有边都加过后，取走n-m+1条余树弦，剩余的（m-1)条边，即构成一棵生成树。,3）加边，即按一定的顺序将边加到图中原位置。每加入一条边都要判断是否构成回路，构成回路，则这条边就是余树弦，将它取走，计入余树弦集合；若新加入的分支未构成回路，说明它是树枝，计入树枝集合；,2）将分支按权排序；,1）将图去边留点；,78,1图论基础-生成树的选择-收缩法,3）收缩法,选择最小树,步骤：1）绘网络图，将节点、分支编号，并标出风向；2）计算生成树枝数和独立回路数，并将边按权大小排序；3）从权最小的分支起，由始点向终点收缩（始点与最小权分支被收缩），将此分支号授于所有与其始点连接的分支，如某分支号重复出现，则消去此分支号；4）如收缩边始末点合一，即构成一个回路。此始末点合一的分支，即为余树弦，将其计入余树弦集；5）如未形成回路，则依次收缩权较小的分支；6）重复5），直到最后一个节点。收缩过程中始末点合一的分支即为余树弦，去掉余树弦后剩余的子图即为最小生成树。收缩过程中形成的回路，即为相应的独立回路。,79,1图论基础-生成树的选择收缩法,步骤：1）从权最小的边1开始收缩,边1与节点B被A吸收,与点B相连的分支5、6均被授于分支号1（如图b)。,例：选择最小树,图a余树弦数与树枝数皆为3，分支按风阻赋权，按风阻升序排列为1,6,4,2,5,3。,A(1)B,80,1图论基础-生成树的选择收缩法,步骤：2）此时未形成回路，依次收缩权小的分支6，D点、边6被A点吸收（如图c)。此时分支3、6、1形成一个回路，分支3始末点重合，为余树弦，将此记于余树弦集内。,A(1)B(6)D,A(1)B(6)D,R1、R6、R4、R2、R5、R3,81,1图论基础-生成树的选择收缩法,步骤：3）然后再收缩分支4，从C向A收缩，点C、边4被A点吸收，分支2与5的始末点均重合，构成两个回路。将收缩边4，(6)，(1)标于与C相连的分支2、5上，形成两个回路是(5，(4)，(6)，(1)，(1)和(2，4，(6)，(1)，前个回路内分支号1重复出现，消去分支号1，该回路实际组成是(5，-4，-6)(图d)。,A(1)B(6)D(4)C,R1、R6、R4、R2、R5、R3,82,1图论基础-生成树的选择收缩法,步骤：4）收缩过程中最后形成回路的分支3、5、2是余树弦。除去余树弦后，剩余的子图即是要求的最小树Tmin=(1,4,6)(图e)。相应的独立回路为(3,6,1)，(5,-4,-6)，(2,4,6,1)。分支前负号表示该分支与余树弦分支风向相反。,83,1图论基础-独立回路选择矩阵运算法,1）矩阵运算法2）试探回朔法3）双通路法,独立回路的选择,84,1图论基础-独立回路选择矩阵运算法,1）矩阵运算法(自学),余树弦在前、树枝在后的顺序，建立基本关联矩阵：,利用关联矩阵与回路矩阵的关系，计算出独立回路矩阵：,85,1图论基础-独立回路选择试探回溯法,2）试探回朔法,前提：生成树和余树弦已知！,思路：往生成树中逐个添加余树弦，根据余树弦的终点找出与之相连的树枝，以此找出一条链，当链的末端是余树弦的始点时，该链即为找出的包含该余树弦回路。,86,1图论基础-独立回路选择试探回溯法,1）取一条余树边作为链，由其终点出发，在树枝中寻找回路的其他分支，当某树枝与该终点相连时，将链终点前移，并记忆该分支；2）判断是否构成回路。当某树枝一端点联接链的终点，另一端点与链的始点重合时，说明已构成回路，转入4）；3）寻找回路组成的进程中，当发现找不到树枝与链的终点相连时，应按原路逐点回朔，在后退中寻找新通路，且将走不通的分支加以记忆；4）当已形成一个回路时，记录回路的组成，且将已联通和不通的记忆标志解除；回路组成中，以余树弦方向为正，与其同向分支为正，逆向分支为负；5）重复上过程，直到形成n-m+1个回路。,方法：,87,1图论基础-独立回路选择试探回溯法,试探回朔法,例,1）生成树：T（1，6，4）2）余树弦：T（2，5，3）3）分支按权升序排列：1，6，4，2，5，34）独立回路数：6413,D,A,B,C,6,4,1,88,1图论基础-独立回路选择试探回溯法,试探回朔法,1）取余树弦3作链，从其终点D出发，沿升序对树枝逐一进行访问，检查各树枝是否与D相连，第一遍访问树枝时，树枝6与D相连，将链的终点前移到B，从B点继续寻找相连的树枝，分支1能与B相连，将链的终点前移到A，此时链的始点与终点重合，形成第一个回路C1（3，6，1）。,例,D,A,B,C,3,6,4,1,R1、R6、R4、R2、R5、R3,89,1图论基础-独立回路选择试探回溯法,D,A,B,C,3,6,4,A,E,F,0层,1层,2层,3层,1,90,1图论基础-独立回路选择试探回溯法,D,A,B,C,6,4,5,1,2）再取余树弦5，从其终点B始，逐一寻找能相连的树枝，对树枝第一遍访问时，分支1能连上，接着从A点继续寻找与之相连的树枝，从图中可以看出，无树枝与A相连，记忆分支1不能通过，将链的终点回朔到B点，重新寻找与B点相连的树枝，跳过树枝1，树枝6能与B相连，将链的终点前移到D，再从D点寻找相连的树枝，联接分支4形成第二条回路C2（5，6，4）注：分支前负号表示其方向与余树弦相反。,试探回朔法,例,91,1图论基础-独立回路选择试探回溯法,试探回朔法,例,D,A,B,C,6,4,2,1,3）最后取余树弦2，从其终点C起，寻找相连的树枝，联分支4，再从D点寻找相连的树枝，联接分支6，再从B点寻找相连的树枝，联接分支1，形成第三个回路C3（2，1，6，4）,92,1图论基础-独立回路选择双通路法,双通路法,选定图的余树和生成树后,任取一节点作为树根，从每一余树弦的始、末点向树根方向寻找通路，当两通路在某一节点处相交时，即形成一个回路，两通路的分支与这条余树弦即为回路的组成。,邻接节点：指与某节点i相邻且靠近树根的节点j；关联分支：是与（i,j)节点对应的树枝k，且规定当k的方向是由ji时为正，由ij时为负,前提条件：生成树和余树弦已知！,93,1图论基础-独立回路选择双通路法,操作步骤：1）指定树根，并计算各节点与树根间的分支数，存入距离数组LEN；2）形成生成树的邻接节点数组INC与关联分支数组NUM：生成树的中某树枝k的始节点为i,未节点为j，若LEN(i)LEN(j),则：INC(j)=i，NUM(j)=k；否则INC(j)=j，NUM(i)=-k3）形成回路4）重复3），直到选出n-m+1个回路为止。,94,1图论基础-独立回路选择,双通路法,例,1,2,3,4,5,6,8,7,9,1）n=9，m=62）生成树：T（2，4，5，6，8）3）余树弦：T（1，3，7，9）4）独立回路数：9614,2,4,5,6,8,95,1图论基础-独立回路选择双通路法,双通路法,例,2,4,5,6,8,1)以节点1作树根，计算各节点与树根间的距离得LEN=(0,1,3,2,3,4),96,1图论基础-独立回路选择双通路法,2,4,5,6,8,2)求生成树的邻接节点数组INC和关联分支数组NUM：INC=（0，1，4，2，4，5）NUM=（0，2，-5，4，6，8）,双通路法,例,97,1图论基础-独立回路选择双通路法,双通路法,例,3)形成独立回路。余树弦1：j1=1，j2=3，LEN(1)=0，LEN(3)=3