图论第二章作业

5、生成树：包含了图中所有节点，且是不含回路的连通图。树枝数（m-1）与余树边（n-m+1）之和等于边数n，由n-m+1条余数弦形成n-m+1个基本回路。

9、基本关联矩阵的特征表示：矩阵内每行的非零元素表示与相应节点关联的分支，1表示流出该节点的分支，-1为流入节点的分支。矩阵每列仅有-1和1组成，分别对应该边的终点和始点，列中仅含有一个非零元素的对应边，即为与该参考点相连的分支。

与生成树的关系：连通图g的基本关联矩阵b的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边，组成g的一棵生成树。

10、基本回路矩阵的每行对应一个独立回路，一个连通图（m，n）的基本回路数为（n-m+1），互异回路数为（2^n-m+1）。

11、基本割集矩阵表示出了生成树的基本割集，基本割集矩阵s的一个大子阵是非奇异的充要条件是这个大子阵的列对应于图的某生成树的树枝。

14、试述破圈法、加边法、收缩法求最小生成树的思路与步骤，并比较其优缺点和使用条件。

破圈法：一、思路。

在一个连通图中，逐次去掉一些边，以破除图中所有回路，则剩下的不含回路的连通图就是图的一棵生成树。如需选择最小树，每次去掉的边应是被破回路中权最大者；如需选最大树，则逐次去掉的边应是被破回路中权最小者；若每次去掉的是任意的一条边，则最后得到一棵任意树。

二、步骤。1) 画网路图，将点、边编号，标出风向。

2) 确定图的余树弦数(即独立回路数)

3) 将分支按权大小排序。

4) 从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选；

5) 重复(4)，直到移去n－m＋1条余树弦，剩余的分支即组成最小风阻树tmin；

三、优缺点。

该法简单、易懂。

四、使用条件。

适于不太复杂的图。

加边法：一、思路。

在图中任取一条边，找一条不与构成回路的边相连，然后再找一条不与构成回路的边相连，如此继续，直到此过程不能进行，这时所得的图就是一棵生成树，若加入的边总是权小的边，可得一最小树；若加入的边总是权大的边，则得最大树；如任意加边，则得一任意树。

二、步骤。1) 将图去边留点；

2) 将分支按权排序；

3) 加边，即按一定顺序将边加到图中原位置。选最大树时，按权从大到小依次将边加入；选最小树时，按权从小到大依次将边加入。每加入一条边都要判断是否构成回路，若新加入的边与已有边构成回路，则这条边就是余树弦，将它取走，计入余树弦集合；若新加入的边与已加入的边未构成回路，说明它是树枝，计入树枝集合；

4) 重复(3)，将所有边都加过后，取走n－m＋1条余树弦，剩余的(m—1)条边，即构成一棵生成树。

三、优缺点。

该法方便易行，简单易懂。

四、使用条件。

可以手工解算，也可以计算机解算。

收缩法：一、思路及步骤。

1) 绘网路图，将节点、分支编号，并标出风向；

2) 计算生成树枝数和独立回路数，并将边按权大小排序；

3) 从权最小的分支起，由始点向终点收缩(始点与最小权分支被收缩)，将此分支号授于所有与其始点连接的分支，如某分支号重复出现，则消去此分支号；

4) 如收缩边始末点合一，即构成一个回路。此始末点合一的分支，即为余树弦，将其计入余树弦集；

5) 如未形成回路，则依次收缩权较小的分支；

6) 重复(5)，直到最后一个节点。收缩过程中始末点合一的分支即为余树弦，去掉余树弦后剩余的子图即为最小生成树。收缩过程中形成的回路，即为相应的独立回路。

如需选择最大树，应从最大权分支开始，依次收缩高权分支即可。对任意连通图，如其顶点为m，则需收缩(m－1)次。

二、优缺点。

此法较复杂，不适于手算。

三、使用条件。

适用于较为额复杂的网络图，适用于电脑解算。