图论基础通风网络

1、课程设置目的,该门课在工程应用中的重要性,1）矿井设计 2）矿井改扩建 3）通风系统调整 4）矿井灾害防治（瓦斯、火,1）风量分配与调整 2）风流方向判断 3）通风设施合理位置的选择 4）灾害烟气蔓延与避灾路线的选择,系统规划系统合并单一风井工作,授课计划,0 绪论 1 图论基础 1.1 图的基本概念 1.2 图的矩阵表示 1.3 生成树选择,2 矿井通风网络 2.1 矿井通风网络图 2.2 矿井通风网络内风流变化的规律 2.3 通风网络分析与数学模型,实验,授课计划,3 通风机运转特性及分析 3.1 扇风机特性的数学描述 3.2 扇风机工况点求解与分析 3.3 用计算机进行扇风机优选,4 复

2、杂通风网络自然分风电算 4.1 复杂通风网络解算概述 4.2 回路法解算复杂风网 4.3 节点法与割集法解算复杂风网 4.4 风网自然分风算法评述 4.5 复杂风网自然分风电算程序实例,实验,授课计划,5 通风网络中风流调节的计算方法 5.1 概述 5.2 独立回路法 5.3 道路法,6 矿井通风网络优化 6.1 矿井通风网络优化概述 6.2 通风网络调节优化 6.3 通风中风量分配的优化 6.4 矿井通风系统优化设计简介,授课计划,7 网络理论在矿井通风中的应用 7.1 在通风设计中的应用 7.2 在通风管理中的应用,8 矿井火灾的通风网络解析 8.1 矿井火灾时期风流状态的变化规律 8.2

3、 矿井火灾时的通风模拟 8.3 矿井火灾时风流控制 8.4 矿井通风模拟软件示例,实验,1 图论基础-图的概念图的定义,顶点或节点,边或分支,图的偶对表示: 图G G(V,E) 节点V V(v1,v2, vm) 节点集 m=|V| 节点数 边E E(e1,e2, em) 边集 n=|E| 边数,1）图的定义 指某类具体事物和这些事物间联系的抽象描述,1.1 图的基本概念,G（m，n,1 图论基础-图的概念图的定义,图的拓扑关系: 顶点和边间的联接关系,有限图 无限图,空图 （m,n)图,根据m,n的值来确定名称,有向图 无向图 混合图,有序，含有有向边,无序,既有有向边，又有无向边,1 图论基

4、础-图的概念图的定义,图的几何表示图的图解,图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,1 图论基础-图的概念图的定义,关联与邻接: 邻接点与邻接边 点、边关联,关联与邻接的区别,v1与e1关联,v5与v6邻接,e2与e3邻接,1 图论基础-图的概念图的定义,平行边（重边,圈,多重图,重边数

5、量叫重数=2,始末点重合的分支,阶,节点个数,完全图,每一对不同节点间均有一条边相连,m阶完全图有多少条边,m(m-1)/2,e10,简单图,1 图论基础-图的概念图的同构,2）图的同构,表示节点和边的关联关系，对其它无限制,GG,应用： 根据需要将通风系统图转变成通风网络图,4,6）图,网络图的美化调整,1 图论基础-图的概念子图,3）子图,真子图,或H中至少有一个边的重数小于G中对应边的重数,且：H中边的重数不超过G中对应边的重数,生成子图,H是包含了图G所有节点的真子图,生成子图是原图的真子图,若,若,且,或,1 图论基础-图的概念子图,课堂练习,根据右图 1）找出3个子图； 2）找出4

6、个真子图； 3）试找出2个生成子图,1 图论基础-图的概念赋权图,4）赋权图,一个图G=（V，E）与定义在E或V上的权或权函数，称为一个网络或赋权图，亦称有权图,在通风网络中，常用通风参数作权的指标，如风阻、风量、风压等。一般将权值注在分支旁边,1 图论基础-道路与回路链,闭合链和开链,1）链,对于图G的p个边e1, e2 , ep ,如果有p+1个顶点序列v1, v2 , vp+1 ,且边ei 与vi -1、 vi 关联（i=1,2p),则这些边构成的序列称为链,ei,vi -1,vi,1 图论基础-道路与回路链,简单链,链,闭链,例,简单链,基本链,没有重复边的链,没有重复顶点的链,1 图

7、论基础-道路与回路路,2）路,路,道路/通路,一条不闭合的基本链,方向一致的路,道路的权,两节点间每条道路内各边的权之和,最长路与最短路,回路,始点和终点重合的基本链,1 图论基础-道路与回路路,课堂练习,根据右图 1）找出经过2号点的2条路； 2）找出3个回路,1 图论基础-道路与回路图的连通性,连通图,非连通图,图G中任意两节点间至少存在一条路,3）图的连通性,多个连通图组成,1 图论基础-道路与回路图的连通性,图的秩,m个节点,k个分离部分，则秩r=m-k 连通图，k=1，则秩为不包含起点的所有节点数,单向连通图,强连通图,vi,vj,vi,vj,任意两个节点间,3）图的连通性,1 图论

8、基础-道路与回路欧拉公式,4）欧拉公式,重点,平面图,把图G画在平面上，各边为简单曲线， 除节点外任意两边均不相交,1 图论基础-道路与回路欧拉公式,4）欧拉公式,网孔f,在自然网眼中，网眼内部 既不含节点，也不含边,欧拉公式,内部回路数C,自然网眼,边围成的区域,f+m-n=2,1 ,C=n-m+1,联系区别,1 图论基础-树树的概念,不含回路的连通图,悬挂点,仅有一条分支与其相关联的节点,割边,去掉后能使图分成两部分的边,割点,去掉与其关联的边后能使图分成两部分的点,树枝,割点与悬挂点有什么关系,1)树T,1 图论基础-树生成树和余树,2)生成树和余树,T是图G的一个生成子图，且是一棵树,

9、包含所有节点；不唯一,生成树,生成树,包含图G全部节点的树,1 图论基础-树生成树和余树,1 图论基础-树生成树和余树,余树,去掉生成树T后，剩下的边构成的子图 余树中即可含有回路，也可不连通,余树弦数,余树中含的边,余树弦,n-m+1,与欧拉公式有何联系,1 图论基础-树生成树和余树,生成树T,1 图论基础-树生成树和余树,特别提醒,任何联通图的边数等于其余树弦数和树枝数之和,图的生成树连通但不含回路,余树既可含回路，也可不连通,任何图的边数等于其余树弦数和树枝数之和,1 图论基础-树生成树和余树,特别提醒,生成树与余树之间的区别,节点数方面,回路方面,连通性方面,1 图论基础-树基本回路,

10、3）基本回路,由一条余树弦和T的树枝构成的回路，称为图G关于生成树T的基本回路,1)基本回路数； 2)基本回路组； 3)回路组非唯一性； 4)基本回路也叫独立回路； 5)回路的方向性,一个图的生成树不唯一基本回路组也不唯一,1 图论基础-树基本回路,3）基本回路,1)基本回路或独立回路数； 2)基本回路组,1 图论基础-树最大树与最小树,4）最大树与最小树,生成树的权,一颗生成树上所有树枝权总和,最大树Tmax,最小树Tmin,1 图论基础-树最大树与最小树,图的最小树是（ ）的树,唯一的,不唯一,权最小,图的最大树是（ ）的树,思考,以上都不是,权最大,1 图论基础-割集割集的定义,割集S是

11、连通图G的边的集合,把S从G中移去,使图G仅成为两部分,但如少移去S中的一条边,则图G仍是连通的,1）割集定义,1）割集为虚线相交的边的集合； 2）边的最小集合； 3）若分成两个以上部分，非割集 割集：S1=d,e,g; S2=a,c,e,g,1 图论基础-割集割集的定义,割点,去除该点后，图分为两个部分,连通图中，除了割点（如3）外，与任一点相连的边的集合均构成一个割集,1 图论基础-割集割集的方向,2）割集方向,1）有向割集； 2）割集正方向的确定； 3）正向边与负向边,以虚线面为界，可把割集内向外穿出的方向定为割集的正方向，也可把割集外向内穿入的方向定为正方向,1 图论基础-割集割集与生

12、成树关系,3）割集与生成树关系,生成树：连通图G的全部节点的最小边集合,割 集：将连通图G的节点分为不相连的二个节点 子集的最少边集合,连通图G的一个割集S至少包含图G的生成树的一条树枝,1 图论基础-割集基本割集,4）基本割集,S1，s2，s3，s4是关于T的基本割集组。 结论：基本割集组是线性无关的,基本割集只能包含一条树枝基本割集数=树枝数,1 图论基础-割集基本割集,1 图论基础-割集基本割集,说明,基本割集只能包含一条树枝基本割集数=树枝数=m-1,基本回路只能包含一条余树弦基本回路数=余树弦数 =n-m+1,重点,1 图论基础-割集基本割集,连通平面图G(m，n,独立回路数为 (,

13、秩为 (,余树弦为 (,n-m+1,m-1,n-m+1,重点,考考你,1 图论基础-割集基本割集,重点,独立回路分支的正负号,基本割集分支的正负号,基本割集内，以树枝方向为准，与其同向者为正，反之为负,独立回路分支方向以余数弦分支方向为准，与其同向者为正，反之为负,1 图论基础-图的矩阵表示邻接矩阵,1）邻接矩阵,表示图的节点间邻接关系的矩阵,构造方阵,其中,1.2 图的矩阵表示,1 图论基础-图的矩阵表示邻接矩阵,例,1）每一行的1表示什么意思？ （2）每一列的1表示什么意思？ （3）非零数的数量与图有什么关系,1 图论基础-图的矩阵表示邻接矩阵,思考,1）如何构造无向图的邻接矩阵,1 图论

14、基础-图的矩阵表示邻接矩阵,思考,2）如何构造非简单有向图的邻接矩阵,1 图论基础-图的矩阵表示关联矩阵,2）关联矩阵,表示图的节点和边的关联关系的矩阵,构造方阵,其中,1）完全关联矩阵,1 图论基础-图的矩阵表示关联矩阵,矩阵Be的行向量是线性相关的，矩阵的秩R=3（4-1,1 图论基础-图的矩阵表示关联矩阵,2）基本关联矩阵,在m阶连通图G的完全关联矩阵Be中,划去任一行后,所得的(m-1)n矩阵,称为图G的基本关联矩阵，简称关联矩阵，记作B。划去的对应点称为参考点,基本关联矩阵线性独立。 通常，通风网络中划去的节点为大气节点,1 图论基础-图的矩阵表示关联矩阵,思考,1）写出下图的关联矩

15、阵,1 图论基础-图的矩阵表示关联矩阵,思考,2）根据下面的关联矩阵，绘制对应的网络图,1 图论基础-图的矩阵表示回路矩阵,3）回路矩阵,表示一个图的边与回路关系的矩阵,1）完全回路矩阵,imax=2n-m+1-1 jmax=n,互异回路：至少有一条边不同的回路,包含图的所有互异回路的矩阵,1 图论基础-图的矩阵表示回路矩阵,回路个数：26-4+1-1=7,1 图论基础-图的矩阵表示回路矩阵,若生成树为T=(2,3,6)，余树弦为（1,4,5,1 图论基础-图的矩阵表示回路矩阵,完全回路矩阵的特点,每一行对应一个回路； 每行非零元素组成一个回路； 行数：2n-m+1; 各行之间并非线性独立；

16、秩为n-m+1（独立回路数,独立回路矩阵能反映完全回路性质，没有必要写完全回路矩阵,1 图论基础-图的矩阵表示回路矩阵,互异回路与独立回路的区别,回路数方面,线性相关方面,独立回路数为n-m+1,互异回路为2n-m+1-1个,独立回路是线性独立的,互异回路则是线性相关的,1 图论基础-图的矩阵表示回路矩阵,2）基本回路矩阵,基本回路矩阵一般是在某个生成树的基础上提出的,imax=n-m+1 jmax=n,若生成树为T=(2,3,6)，余树弦为（1,4,5,1 图论基础-图的矩阵表示回路矩阵,1)基本回路矩阵的秩等于：n-m+1 2)余树弦在前、树枝在后分为两部分,生成树为T=(2,3,6)，余

17、树弦为（1,4,5,基本回路矩阵的性质,1 图论基础-图的矩阵表示割集矩阵,4）割集矩阵,1）完全割集矩阵,表达图的边与割集关系的矩阵,包含图G的全部割集的矩阵,1 图论基础-图的矩阵表示割集矩阵,1 图论基础-图的矩阵表示割集矩阵,取生成树,余树弦,可发现,1 图论基础-图的矩阵表示割集矩阵,2）基本割集矩阵,同一个图，有不同的生成树，故基本割集也不相同,列：余树在前，树枝在后； 行：按树枝在矩阵内的列序排序,1 图论基础-图的矩阵表示矩阵间关系,5）矩阵间关系(自学,生成树,余树弦,关联矩阵,1 图论基础-图的矩阵表示矩阵间关系,生成树,余树弦,回路矩阵,1 图论基础-图的矩阵表示矩阵间关

18、系,生成树,余树弦,割集矩阵,1 图论基础-图的矩阵表示矩阵间关系,关联矩阵B与回路矩阵C的关系,回路矩阵C与割集矩阵S的关系,割集矩阵S与割集矩阵的关系,1 图论基础-生成树的选择,1.3生成树的选择,知识点 生成树的选择 独立回路的选择,既是本章重点 又是本章难点,1 图论基础-生成树的选择,最大树,最小树,任意树,生成树的类型,根据权值大小进行划分,1 图论基础-生成树的选择,破圈法,加边法,收缩法,生成树的选择方法,常用,1 图论基础-生成树的选择破圈法,1）破圈法,1）画网络图,将点、边编号，标出风向：m=4 ,n=6 2）确定图的余树弦数（即独立回路数）N: N=n-m+1=3 3

19、）将分支按权（风阻）大小排序：R1、 R6、 R4、 R2、 R5、 R3 4）从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选； 5）重复4），直到移去n-m+1条余树弦，剩余的分支即组成最小风阻树Tmin,选择最小树,为什么可能是独立回路,1 图论基础-生成树的选择破圈法,为什么可能是独立回路,D,A,B,C,3,6,4,2,5,1,以分支3为例： 去掉分支3,3个回路被破坏,哪个是独立回路,4,1 图论基础-生成树的选择破圈法,注意：若被破坏的回路中，有一条以上高阻分支，应重选,D,A,B,C,6,1,R1、 R6、 R

20、4、 R2、 R5、 R3,以分支3为例,如果,4,1 图论基础-生成树的选择破圈法,破圈法选择最小树,D,A,B,C,6,4,1,高阻分支：3，5，2 最小风阻树: Tmin=(1，6，4) 余树弦： ， ， 独立回路（ ，1，6） （ ，-4，-6） （ ，1，4，6,1 图论基础-生成树的选择破圈法,结果检验: 每加入一条余树弦，便构成一个独立回路,D,A,B,C,6,4,1,1 图论基础-生成树的选择破圈法,思考,V1,V2,V3,V4,V5,e1,e2,e5,e3,e4,e6,e7,用破圈法找出左图最大树,各分支风阻大小升序为：e6，e2，e3，e1，e7，e4，e5,1 图论基础-

21、生成树的选择加边法,2）加边法,加边法选择最大树,D,A,B,C,R1、 R6、 R4、 R2、 R5、 R3,4）重复3），将所有边都加过后，取走n-m+1条余树弦，剩余的（m-1)条边，即构成一棵生成树,3）加边，即按一定的顺序将边加到图中原位置。每加入一条边都要判断是否构成回路，构成回路，则这条边就是余树弦，将它取走，计入余树弦集合；若新加入的分支未构成回路，说明它是树枝，计入树枝集合,2）将分支按权排序,1）将图去边留点,1 图论基础-生成树的选择-收缩法,3）收缩法,选择最小树,步骤： 1）绘网络图，将节点、分支编号，并标出风向； 2）计算生成树枝数和独立回路数，并将边按权大小排序；

22、 3）从权最小的分支起，由始点向终点收缩（始点与最小权分支被收缩），将此分支号授于所有与其始点连接的分支，如某分支号重复出现，则消去此分支号； 4）如收缩边始末点合一，即构成一个回路。此始末点合一的分支，即为余树弦，将其计入余树弦集； 5）如未形成回路，则依次收缩权较小的分支； 6）重复5），直到最后一个节点。 收缩过程中始末点合一的分支即为余树弦，去掉余树弦后剩余的子图即为最小生成树。收缩过程中形成的回路，即为相应的独立回路,1 图论基础-生成树的选择收缩法,步骤： 1）从权最小的边1开始收缩,边1与节点B被A吸收,与点B相连的分支5、6均被授于分支号1（如图b,例：选择最小树,图a余树弦数

23、与树枝数皆为3，分支按风阻赋权，按风阻升序排列为1,6,4,2,5,3,A(1)B,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,1 图论基础-生成树的选择收缩法,步骤： 3）然后再收缩分支4，从C向A收缩，点C、边4被A点吸收，分支2与5的始末点均重合，构成两个回路。将收缩边4，(6)，(1)标于与C相连的分支2、5上，形成两个回路是(5，(4)，(6)，(

24、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,1 图论基础-生成树的选择收缩法,步骤： 4）收缩过程中最后形成回路的分支3、5、2是余树弦。除去余树弦后，剩余的子图即是要求的最小树Tmin=(1,4,6)(图e)。相应的独立回路为(3,6,1)，(5,-4,-6)，(2,4,6,1)。分支前负号表示该分支与余树弦分支风向相反,1 图论基础-独立回路选择矩阵运算法,1）矩阵运算法 2）试探回朔法 3）双通路法,独立回路的选择,1 图论基础-独立回

25、路选择矩阵运算法,1）矩阵运算法(自学,余树弦在前、树枝在后的顺序，建立基本关联矩阵,利用关联矩阵与回路矩阵的关系，计算出独立回路矩阵,1 图论基础-独立回路选择试探回溯法,2）试探回朔法,前提：生成树和余树弦已知,思路：往生成树中逐个添加余树弦，根据余树弦的终点找出与之相连的树枝，以此找出一条链，当链的末端是余树弦的始点时，该链即为找出的包含该余树弦回路,1 图论基础-独立回路选择试探回溯法,1）取一条余树边作为链，由其终点出发，在树枝中寻找回路的其他分支，当某树枝与该终点相连时，将链终点前移，并记忆该分支； 2）判断是否构成回路。当某树枝一端点联接链的终点，另一端点与链的始点重合时，说明已

26、构成回路，转入4）； 3）寻找回路组成的进程中，当发现找不到树枝与链的终点相连时，应按原路逐点回朔，在后退中寻找新通路，且将走不通的分支加以记忆； 4）当已形成一个回路时，记录回路的组成，且将已联通和不通的记忆标志解除；回路组成中，以余树弦方向为正，与其同向分支为正，逆向分支为负； 5）重复上过程，直到形成n-m+1个回路,方法,1 图论基础-独立回路选择试探回溯法,试探回朔法,例,1）生成树：T（1，6，4） 2）余树弦：T（2，5，3） 3）分支按权升序排列： 1，6，4，2，5，3 4）独立回路数：6413,D,A,B,C,6,4,1,1 图论基础-独立回路选择试探回溯法,试探回朔法,1

27、）取余树弦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,1 图论基础-独立回路选择试探回溯法,D,A,B,C,3,6,4,A,E,F,0层,1层,2层,3层,1,1 图论基础-独立回路选择试探回溯法,D,A,B,C,6,4,5,1,2）再取余树弦5，从其终点B始，逐一寻找能相连的树枝，对树枝第一遍访问时，分支1能

28、连上，接着从A点继续寻找与之相连的树枝，从图中可以看出，无树枝与A相连，记忆分支1不能通过，将链的终点回朔到B点，重新寻找与B点相连的树枝，跳过树枝1，树枝6能与B相连，将链的终点前移到D，再从D点寻找相连的树枝，联接分支4形成第二条回路 C2（5，6，4） 注：分支前负号表示其方向与余树弦相反,试探回朔法,例,1 图论基础-独立回路选择试探回溯法,试探回朔法,例,D,A,B,C,6,4,2,1,3）最后取余树弦2，从其终点C起，寻找相连的树枝，联分支4，再从D点寻找相连的树枝，联接分支6，再从B点寻找相连的树枝，联接分支1，形成第三个回路 C3（2，1，6，4,1 图论基础-独立回路选择双通

29、路法,双通路法,选定图的余树和生成树后,任取一节点作为树根，从每一余树弦的始、末点向树根方向寻找通路，当两通路在某一节点处相交时，即形成一个回路，两通路的分支与这条余树弦即为回路的组成,邻接节点：指与某节点i相邻且靠近树根的节点j； 关联分支：是与（i,j)节点对应的树枝k，且规定当k的方向是由ji时为正，由ij时为负,前提条件：生成树和余树弦已知,1 图论基础-独立回路选择双通路法,操作步骤： 1）指定树根，并计算各节点与树根间的分支数，存入距离数组LEN； 2）形成生成树的邻接节点数组INC与关联分支数组NUM： 生成树的中某树枝k的始节点为i,未节点为j，若LEN(i)LEN(j),则：

30、 INC(j)=i，NUM(j)=k；否则INC(j)=j， NUM(i)=-k 3）形成回路 4）重复3），直到选出n-m+1个回路为止,1 图论基础-独立回路选择,双通路法,例,1,2,3,4,5,6,8,7,9,1）n=9，m=6 2）生成树：T（2，4，5，6，8） 3）余树弦：T（1，3，7，9） 4）独立回路数：9614,2,4,5,6,8,1 图论基础-独立回路选择双通路法,双通路法,例,2,4,5,6,8,1)以节点1作树根，计算各节点与树根间的距离得LEN=(0,1,3,2,3,4,1 图论基础-独立回路选择双通路法,2,4,5,6,8,2)求生成树的邻接节点数组INC 和关联分支数组NUM： INC=（0，1，4，2，4，5） NUM=（0，2，-5，4，6，8,双通路法,例,1 图论基础-独立回路选择双通路法,双通路法,例,3)形成独立回路。 余树弦1：j1=1，j2=3，LEN(1)=0，LEN(3)=3，故采用后通路法 P1(1)=-