资源描述：
《矩阵最小生成树算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、.作业总结第一组组员：王重阳张星康煜问题：一：矩阵及特殊矩阵算法整理二：树、支撑树、最小树等相关概念及性质三：最小生成树算法及其应用（比拳法、破圈法）总结：一．几种特殊类型矩阵：1.三角矩阵：（1）定义：如果n阶矩阵主对角线下（上）方元素全部等于零，则称此矩阵为上（下）三角矩阵。（2）性质：若A与B为n阶上（下）三角矩阵，k为任意实数，则：①A-+B也是上（下）三角矩阵;②kA也是上（下）三角矩阵；③AB也是上（下）三角矩阵。A=a11a12…a1n0a22…a2n…………00…ann2.对角矩阵：（1）定义：除对角线元素之外所有的元素均为零的n阶矩
2、阵称为对角矩阵。（2）性质：①两个同阶对角矩阵的和（差）仍是对角矩阵;②数乘对角矩阵仍是对角矩阵；③两个同阶对角矩阵的乘积仍是对角矩阵，且满足交换律；④对角矩阵与它的转置矩阵相等，即A=AT.A=a110…00a22…0…………00…ann3.单位矩阵：定义：如果数量矩阵中元A=1，称该矩阵为N阶单位矩阵，记作En,简记为:E.100010001...1.对称矩阵和反对称矩阵：对称矩阵：（1）定义：如果阶矩阵A满足AT=A，则称A为对称矩阵。（2）性质：①如果A，B均为n阶矩阵，则A-+B也是对称矩阵;②数k与对称矩阵的乘积kA也是对称矩阵.反对称矩
3、阵：（1）定义：如果阶矩阵A满足AT=-A，则称A为反对称矩阵。（2）性质：①设A，B均为n阶反对称矩阵，则A-+B仍是反对称矩阵；②数与反对称矩阵的乘积仍是反对称矩阵。2.数量矩阵：（1）定义：如果n阶对角矩阵所有主对角线元素都相等，则称此矩阵为n阶数量矩阵，一般记为a…00a…0⋯an（2）性质：用数量矩阵A右（左）乘矩阵B，其结果为用A的主对角线上的元素a乘以矩阵B。即若数量矩阵A=a…00a…0⋯anABm*n=AB(Cn*mA=aC).二．树、支撑树、最小树等相关概念及性质1.支撑树：图G的一个支撑子图(spanningsubgraph)是
4、一个含有G的所有节点的子图。如果图G的支撑子图是一棵树，则称为G的支撑树(spanningTree)，或者称为生成树。我们通常说的最小生成树(minimalspanningtree)就是指图G的所有支撑树中边权之和最小的支撑树。2.：最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边,这就是最小生成树。3.树：树n(n≥0)是个结点的有限集合，当n=0时是空树，当n>0时，是非空树，它满足以下两个条件：...（1）有且仅有一个称为根的结点；（2）其余结点分为m（m≥0）个互不
5、相交的非空集合T1，T2，…Tm，其中每个集合本身又是一棵树,称为根的子数.三．最小生成树的算法及应用：避圈法：1理论根据1.1约化原则给定一无向连通图G=（V,E）（V表示顶点，E表示边），其中V={,,……},E={,,……}对于G中的每条边eE都赋予权（）>0，求生成树T=（V,H），HE，使生成树所有边权最小，此生成树称为最小生成树．（1）基本回路将属于生成树T中的边称为树枝，树枝数为n-1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为。基本回路是由T中的树枝和一条连枝构成的回路．（2）基本
6、割集设无向图G的割集S（割集是把连通图分成两个分离部分的最少支路集合），若S中仅包含有T中的一条树枝，则称此割集为基本割集，记为。基本割集是集合中的元素只有一条是树枝，其他的为连枝．（3）等长变换设T=(V,H),为一棵生成树，eH,E,H,当且仅当，也就是说e，则=T{e,}也是一棵生成树。当=时，这棵生成树叫做等长变换。等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树．根据以上定理得出2个结论：①若在某个回路C中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边e的割集中有一条唯一最短边，则每棵生成树中都必须
7、含这条边．由上面结论可以得到唯一性：若图G中的生成树T=（V,H）是唯一的一棵最小生成树，当且仅当任意一连枝eH,E都是其基本回路中唯一最长边，任意一条树边e都是其基本割集中的唯一最短边．由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树。对于中每一条树边eH，若e是基本割集中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。...对于每条连枝eH,E，若它是基本回路中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去．约化原则是在最小生成树不唯一的情况下，从已经得到的一棵
8、最小生成树中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边．在基本回路中若
