图论基础通风网络.ppt

课程设置目的 授课计划 0 绪论 1 图论基础 1.1 图的基本概念 1.2 图的矩阵表示 1.3 生成树选择 授课计划 3 通风机运转特性及分析 3.1 扇风机特性的数学描述 3.2 扇风机工况点求解与分析 3.3 用计算机进行扇风机优选 授课计划 5 通风网络中风流调节的计算方法 5.1 概述 5.2 独立回路法 5.3 道路法 授课计划 7 网络理论在矿井通风中的应用 7.1 在通风设计中的应用 7.2 在通风管理中的应用 1）图的定义 指某类具体事物和这些事物间联系的抽象描述。 图的拓扑关系: 顶点和边间的联接关系。 图的几何表示——图的图解 关联与邻接: 邻接点与邻接边 点、边关联 1)树T 生成树: 说明: 1）邻接矩阵 2）关联矩阵 3）回路矩阵 4）割集矩阵 5）矩阵间关系(自学) 1.3生成树的选择 知识点 生成树的选择 独立回路的选择 生成树的类型 生成树的选择方法 1）破圈法 2）加边法 3）收缩法 1）矩阵运算法 2）试探回朔法 3）双通路法 1）矩阵运算法(自学) 2）试探回朔法 1 图论基础----图的矩阵表示—割集矩阵 1 图论基础----图的矩阵表示—割集矩阵 取生成树 余树弦 可发现 1 图论基础----图的矩阵表示—割集矩阵 （2）基本割集矩阵 同一个图，有不同的生成树，故基本割集也不相同。 列：余树在前，树枝在后； 行：按树枝在矩阵内的列序排序 1 图论基础----图的矩阵表示—矩阵间关系 生成树 余树弦 关联矩阵 V1 V2 V3 V4 V5 e1 e2 e5 e3 e4 e6 e7 1 图论基础----图的矩阵表示—矩阵间关系 生成树 余树弦 回路矩阵 V1 V2 V3 V4 V5 e1 e2 e5 e3 e4 e6 e7 1 图论基础----图的矩阵表示—矩阵间关系 生成树 余树弦 割集矩阵 V1 V2 V3 V4 V5 e1 e2 e5 e3 e4 e6 e7 1 图论基础----图的矩阵表示—矩阵间关系 V1 V2 V3 V4 V5 e1 e2 e5 e3 e4 e6 e7 关联矩阵B与回路矩阵C的关系 回路矩阵C与割集矩阵S的关系 割集矩阵S与割集矩阵的关系 1 图论基础----生成树的选择 既是本章重点 又是本章难点 1 图论基础----生成树的选择 最大树 最小树 任意树 根据权值大小进行划分 L1 L3 L2 L4 L5 L6 1 图论基础----生成树的选择 破圈法 加边法 收缩法 常用 2 5 3 1 图论基础----生成树的选择—破圈法 6 2 1）画网络图,将点、边编号，标出风向：m=4 ,n=6 2）确定图的余树弦数（即独立回路数）N: N=n-m+1=3 3）将分支按权（风阻）大小排序：R1、 R6、 R4、 R2、 R5、 R3 4）从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选； 5）重复4），直到移去n-m+1条余树弦，剩余的分支即组成最小风阻树Tmin 选择最小树 为什么可能是独立回路？ 3 4 5 1 C D B A 1 图论基础----生成树的选择—破圈法 为什么可能是独立回路？ D A B C 3 6 4 2 5 1 以分支3为例： 去掉分支3 3个回路被破坏,哪个是独立回路？ 4 1 图论基础----生成树的选择—破圈法 注意：若被破坏的回路中，有一条以上高阻分支，应重选！ D A B C 6 1 3 2 5 R1、 R6、 R4、 R2、 R5、 R3 以分支3为例： 如果： 4 1 图论基础----生成树的选择—破圈法 破圈法选择最小树 D A B C 6 4 1 3 2 5 高阻分支：3，5，2 最小风阻树: Tmin=(1，6，4) 余树弦： ③， ⑤， ② 独立回路（ ③，1，6） （ ⑤ ，-4，-6） （ ② ，1，4，6） D A B C 3 6 4 2 5 1 1 图论基础----生成树的选择—破圈法 结果检验: 每加入一条余树弦，便构成一个独立回路。 D A B C 6 4 1 3 2 5 1 图论基础----生成树的选择—破圈法 思考 V1 V2 V3 V4 V5 e1 e2 e5 e3 e4 e6 e7 用破圈法找出左图最大树。 各分支风阻大小升序为：e6，e2，e3，e1，e7，e4，e5 1 图论基础----生成树的选择—加边法 加边法选择最大树 D A B C 3 2 6 5 4 1 R1、 R6、 R4、 R2、 R5、 R3 4）重复3），将所有边都加过后，取走n