基本关联矩阵及其性质.ppt

《基本关联矩阵及其性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2基本关联矩阵及其性质一、树：连通、无回路、每边是割边、n-1条边二、至少有两个度数为1的结点(叶子)三、矩阵线性无关最大行数=矩阵线性无关最大列数=矩阵中非零的方阵的最大阶数=列对应图中边，最大线性无关的边数四、回路中的边线性k相关，对应的列线性相关，这些列中任意K阶子式为0本节讨论对象为有向连通图G定义3.2.1基本关联矩阵:在有向连通图G的关联矩阵B中划去任意结点Vk所对应的行,得到一个(n-1)×m的矩阵Bk,称为G的一个基本关联矩阵.V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10V1V2V3V4V5V6e2e1e3e4e5e6e7e8

2、e9e10V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10Th3.2.1有向图G的关联矩阵B的秩

3、1=0det(S2)=a22=1、0、-1若a11=1,a21=-1det(S2)=a22+a12，第2列中两元可能:1与-1、1或-1、全0。若a11=-1,a21=1det(S2)=-a22-a12=-(a22+a12)同上。若a11=-1,a21=0det(S2)=-a22=1、0、-1若a11=0,a21=1det(S2)=-a12=1、0、-1若a11=0,a21=-1det(S2)=a12=1、0、-1Th3.2.2设S是有向图的关联矩阵B任一k阶方阵,则Det(S)=0,1或-1.证明：假设n=k时，det(Sk)=1、0、-1.对于(k+1)阶方阵S，

4、由于关联矩阵的每列只有2个非0元即+1,-1,故S的每列最多只有2个非0元+1,-1。S的情况如下：(1)S有一列全为0则det(S)=0。(2)每列都不全为0，即每列都有非0元。(2.1)每列都有两个非零元即每列都有+1、-1，则将前k行加到第k+1行，则使得第k+1行为0，故det(S)=0。(2.2)某一列只有一个非零元aij，则按其展开为det(S)=aij*(-1)i+jdet(Sk)=(-1)i+jdet(Sk)=1,0,-1各阶子式的值是0,-1,+1.定理3.2.3连通图G有n个结点，点与边的完全关联矩阵的秩为n-1。证明：线性无关的最大行数为n-1

5、，再多1行即n行就相关，即线性相关的最少行数为n，用反证法证明。即假设线性相关的最少行数为L

6、全0的调整到后面.最后将这L行调整到最前面。定理3.2.3连通图G有n个结点，点与边的完全关联矩阵的秩为n-1。证:假设线性相关的最少行数为L0

7、，则B'至少分为两个连通分枝，而B'仅是B进行“行-行”与“列-列”互换得到,是改变点与边在关联矩阵中出现的顺序，故保持连接性不变，故B也有2个连通分枝，故原图G不连接.与原图是连通矛盾！故线性相关至少需要n行，小于n无关，线性无关最大行数为n-12个非0元的列全0元的列定理3.2.4连通图基本关联矩阵Bk的秩n-1.证明:由定理3.2.3的证明可知,线性相关的行数至少为n，故小于n则线性无关。即任意n-1行肯定线性无关，而Bk是关联矩阵的某n-1行，故线性无关，故Bk的秩为n-1。说明：若G的结点为n，连通分支数为w，则完全关联矩阵的秩为n-w。分