图论基础通风网络.pptVIP

1图论基础----图的矩阵表示—割集矩阵1图论基础----图的矩阵表示—割集矩阵取生成树余树弦可发现1图论基础----图的矩阵表示—割集矩阵（2）基本割集矩阵同一个图，有不同的生成树，故基本割集也不相同。列：余树在前，树枝在后；行：按树枝在矩阵内的列序排序*1图论基础----图的矩阵表示—矩阵间关系5）矩阵间关系(自学)生成树余树弦关联矩阵V1V2V3V4V5e1e2e5e3e4e6e7*1图论基础----图的矩阵表示—矩阵间关系生成树余树弦回路矩阵V1V2V3V4V5e1e2e5e3e4e6e7*1图论基础----图的矩阵表示—矩阵间关系生成树余树弦割集矩阵V1V2V3V4V5e1e2e5e3e4e6e71图论基础----图的矩阵表示—矩阵间关系V1V2V3V4V5e1e2e5e3e4e6e7关联矩阵B与回路矩阵C的关系回路矩阵C与割集矩阵S的关系割集矩阵S与割集矩阵的关系1图论基础----生成树的选择*3生成树的选择知识点生成树的选择独立回路的选择既是本章重点又是本章难点1图论基础----生成树的选择*最大树最小树任意树生成树的类型根据权值大小进行划分L1L3L2L4L5L61图论基础----生成树的选择*破圈法加边法收缩法常用生成树的选择方法2531图论基础----生成树的选择—破圈法1）破圈法621）画网络图,将点、边编号，标出风向：m=4,n=62）确定图的余树弦数（即独立回路数）N:N=n-m+1=33）将分支按权（风阻）大小排序：R1、R6、R4、R2、R5、R34）从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选；5）重复4），直到移去n-m+1条余树弦，剩余的分支即组成最小风阻树Tmin选择最小树为什么可能是独立回路？3451CDBA1图论基础----生成树的选择—破圈法为什么可能是独立回路？DABC364251以分支3为例：去掉分支33个回路被破坏,哪个是独立回路？41图论基础----生成树的选择—破圈法注意：若被破坏的回路中，有一条以上高阻分支，应重选！DABCR1、R6、R4、R2、R5、R3以分支3为例：如果：1图论基础----树—生成树和余树*特别提醒1任何联通图的边数等于其余树弦数和树枝数之和2图的生成树连通但不含回路3余树既可含回路，也可不连通4任何图的边数等于其余树弦数和树枝数之和51图论基础----树—生成树和余树*0201030405生成树与余树之间的区别特别提醒节点数方面连通性方面回路方面1图论基础----树—基本回路*3）基本回路由一条余树弦和T的树枝构成的回路，称为图G关于生成树T的基本回路。1)基本回路数；2)基本回路组；3)回路组非唯一性；4)基本回路也叫独立回路；5)回路的方向性一个图的生成树不唯一→基本回路组也不唯一V3V1V2V4V5e1e2e3e4e5e6e7e81图论基础----树—基本回路*e93）基本回路1)基本回路或独立回路数；2)基本回路组；32456e1e2e3e4e5e6e7e81图论基础----树—最大树与最小树最大树与最小树生成树的权：一颗生成树上所有树枝权总和。最大树Tmax最小树Tmin1图论基础----树—最大树与最小树图的最小树是（）的树。唯一的不唯一权最小图的最大树是（）的树。思考以上都不是权最大1图论基础----割集—割集的定义*割集S是连通图G的边的集合,把S从G中移去,使图G仅成为两部分,但如少移去S中的一条边,则图G仍是连通的。1）割集定义12354bfgdacS4eS1S2S31）割集为虚线相交的边的集合；2）边的最小集合；3）若分成两个以上部分，非割集割集：S1={d,e,g};S2={a,c,e,g}1图论基础----割集—割集的定义*割点去除该点后，图分为两个部分。连通图中，除了割点（如3）外，与任一点相连的边的集合均构成一个割集。142356712354bfgdacS4eS1S2S31图论基础---