最小生成树
顶点j不直接相连，则Aij=0。对角线元素Aii=0。
从理论上来讲，由与各顶点相连的最短边构成的生成树，其每条边的权值和一定最小。所以，首先找出与各个顶点相连的权值最小的边。即在权矩阵A中按行找出非零最小元。若一行中同时出现两个非零最小元，说明离该点有两个最近点，即与该点相连的所有边里有两条权值最小的边，可随便选一个。如果找出的所有非零最小元中同时出现Aij与Aji，表示离顶点i最近的是点j，而离点j最近的是点i。则任意去掉Aij、Aji中的一个。然后统计非零最小元的个数k。至此可以得到这样几个结论：①这k个非零最小元的脚标的并集必然包括了1，2，3……n，即由这k个非零最小元分别对应的边构成的图有n个顶点；②k≦n-1；③构成的图没有回路。
假设与各个顶点相连的最短边互不重合，即在形成的权矩阵中按行寻找到的非零最小元个数为4。假设与点1相连的所有边中a13最小；与点2相连的所有边中a23最小；与点3相连的所有边中a34最小；与点4相连的所有边中a41最小。从而有
，a13＜a14（1B）23＜a21（2A），a23＜a24a13＜a12（1A）
（2B）；
a34＜a32（3A），a34＜a31（3B）；a41＜a42（4A），a41＜a43（4B）。
根据aij=aji以及上述关系式中的（1B）（4B）（3B），可以得出a13＜a14＜a34＜a31。因为a13=a31，所以上式不成立。即在形成的权矩阵中按行寻找到的非零元个数不可能为4（更不可能比4大，
搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高等教育毕业论文初稿(7)全文阅读和word下载服务。
相关推荐：
骤雨初歇