毕业论文初稿(7)

最小生成树

顶点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大，