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

3.2基本关联矩阵及其性质 一、树：连通、无回路、每边是割边、n-1条边 二、至少有两个度数为1的结点(叶子) 三、矩阵线性无关最大行数= 矩阵线性无关最大列数= 矩阵中非零的方阵的最大阶数= 列对应图中边，最大线性无关的边数 四、回路中的边线性k相关，对应的列线性相关，这些列中任意K阶子式为0 本节讨论对象为有向连通图G 定义3.2.1基本关联矩阵:在有向连通图G的关联矩阵B中划去任意结点Vk所对应的行,得到一个(n-1)×m的矩阵Bk,称为G的一个基本关联矩阵. Th3.2.1有向图G的关联矩阵B的秩n 证明 由于矩阵B的每列表示每边的起点与终点,起点处为1,终点为-1. 行1+行2+…+行n=0,故 行n=-行1-行2-…-行n-1，即行n为前n-1的线性组合，即行n与前n-1行不独立,故独立行数即B的秩n. Th3.2.2设S是有向图的关联矩阵B任一k阶方阵,则Det(S)=0,1或-1. 证明 当k=1时det(S1)=1、0、-1. 当k=2时det(S2)=1、0、-1. det(S2)=a11*a22-a21*a12 v1是边e1的起终无 若a11=1,a21=0 det(S2)=a22=1、0、-1 若a11=1,a21=-1 det(S2)=a22+a12，第2列中两元可能:1与-1、1或-1、全0。 若a11=-1,a21=1 det(S2)=-a22-a12=-(a22+a12)同上。 若a11=-1,a21=0 det(S2)=-a22=1、0、-1 若a11=0,a21=1 det(S2)=-a12=1、0、-1 若a11=0,a21=-1 det(S2)=a12=1、0、-1 Th3.2.2设S是有向图的关联矩阵B任一k阶方阵,则Det(S)=0,1或-1. 证明： 假设n=k时，det(Sk)=1、0、-1. 对于(k+1)阶方阵S，由于关联矩阵的每列只有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.4 连通图基本关联矩阵Bk的秩n-1. 证明: 由定理3.2.3的证明可知,线性相关的行数至少为n，故小于n则线性无关。 即任意n-1行肯定线性无关，而Bk是关联矩阵的某n-1行，故线性无关，故Bk的秩为n-1。 说明： 若G的结点为n，连通分支数为w，则完全关联矩阵的秩为n-w。 分支数w=点数n-关联矩阵的秩rank(B) 特别是w=1即G连通时,秩为n-1 点数是确定的，关联矩阵随网络连接情况而变化，故根据其秩数可判断网络的连通性。 推论3.2.1 n个结点树T的基本关联矩阵的秩是n-1. 证明:T是连通无回路的图，是一个特殊的连通图。 给每条边加上方向，父结点为边的起点，子结点为边的终点，则树T是有向连通图。 根据定理3.2.3可知，故它的基本关联矩阵的秩是n-1. 有向图的连通性,是在忽略每边的方向后确定的,这与其它教材上关于有向图的定义不一样,请注意. 结点数为n的连通图G的基本关联矩阵的秩是n-1,其中边数最少的连通图是“树”,它恰好有n-1边,这n-1边是线性无关的. 其它连通图中的边数n-1,而这些边中又只有n-1列是线性无关的,那么哪些列是线性无关的呢?如何寻找呢？ 定理3.2.5 C是连通图G的一个回路,Bk是G的一个基本关联矩阵,那么回路C中各点与各边对应Bk的列线性相关. 一个回路中的边是线性相关的。 回路矩阵能找出所有相关、无关边 设初级回路C包含了G的L个结点，由点与边均不重复，C肯定有L条边,这L条边对应关联矩阵B的L列,这L列构成B的子阵B(Gc)，环C本身的关联矩阵B(C) (L点L边)。 证明:只需针对初级回路进行讨论. 设回路C包含了G的L个结点L条边. 不妨假设Ln,这L条边对应关联矩阵B的L列,这L列构成B的子阵B(Gc). 回路C的关联矩阵B(C) 是L阶方阵,又由于C是连通图,故B(C)的秩为L-1. 由秩的定义可知，矩阵B(C)的L个列向量线性相关。 而基本关联