基本关联矩阵及其性质.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*a12v1是边e1的起终无若a11=1,a21=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、-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.3连通图G有n个结点，点与边的完全关联矩阵的秩为n-1。证明：线性无关的最大行数为n-1，再多1行即n行就相关，即线性相关的最少行数为n，用反证法证明。即假设线性相关的最少行数为Ln，寻找错误的结论。,定理3.2.3连通图G有n个结点，点与边的完全关联矩阵的秩为n-1。证:假设线性相关的最少行数为Ln.k1b(i1)+k2b(i2)+kLb(iL)=0ki0,i=1L因关联矩阵每列只有二个非0元，则这L行所形成的矩阵中每列至多有2个非0元，有些列可能全是0，但不可能只有1个非0元。假设某列j只有1个非0元在ki行，则该列各数的线性组合=ki*bij=ki=0，与ki0矛盾.对关联矩阵的列进行调整，将这L行中列中含有2个非0元的列调整最前面，全0的调整到后面.最后将这L行调整到最前面。,定理3.2.3连通图G有n个结点，点与边的完全关联矩阵的秩为n-1。证:假设线性相关的最少行数为Ln.对关联矩阵的列进行调整，将这L行中列中含有2个非0元的列调整最前面，全0的调整到后面.最后将这L行调整到最前面。记L行中含2个非0元的列数为t，即这L行只与这t条边相关，则有如下分块矩阵：,定理3.2.3连通图G有n个结点，关联矩阵的秩为n-1。证:假设线性相关的最少行数为Ln-1,而这些边中又只有n-1列是线性无关的,那么哪些列是线性无关的呢?如何寻找呢？定理3.2.5C是连通图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个列向量线性相关。而基本关联矩阵Bk中与这L条边对应的L列向量的下方(即n-L-1行)全是0(因这L条边只与回路C中的L个结点相关,与其他点无关故为0)，故Bk中这L个列也线性相关。,推论3.2.2设H是连通图G的子图,若H含有回路,则H的诸边对应的G的基本关联矩阵各列线性相关.减少找回路范围定理3.2.2令Bk是有向连通图G的基本关联矩阵,Bk的某n-1阶子阵行列式非0其各列对应的边构成一棵支撑树。不在某回路上!,定理3.2.2令Bk是有向连通图G的基本关联矩阵,那么Bk的某n-1阶子阵行列式非0的是其各列所对应的边构成G的支撑树.证明:.如果某个N-1阶子阵Bk(GT)的行列式非0,则这n-1列线性无关,即这n-1边线性无关。由推理3.2.2可知,则这n-1条边中不含回路(若有回路则线性相关)。由树的定义含有n-1条不构成回路的边，即构成一棵树，即为支撑树。,定理3.2.2令Bk是有向连通图G的基本关联矩阵,那么Bk的某n-1阶子阵行列式非0的是其各列所对应的边构成G的支撑树.证明:.设对应边的构成一棵树,则由树的定义可知,它有n-1条边无回路,则这些边线性无关,对应的列向量线性无关。基本关联矩阵Bk(T)只有n-1行，因此这n-1行与树中的n-1边所对应的列向量构成n-1阶方阵。由线性代数知识可知，线性无关的n-1列所对应的n-1阶行列式值不等于0。,定理3.2.2令Bk是有向连通图G的基本关联矩阵,那么Bk的某n-1阶子阵行列式非0的是其各列所对应的边构成G的支撑树.此定理说明，基本关联矩阵Bk中，n-1阶非0子式的个数，为G的生成树的棵数。而Bk恰好有n-1行,关键是寻找n-1个线性无关的列,构成树的边的组合是其对应子式非0.下一节，将介绍基于基本关联矩阵计算生成树棵数的方法、写出生成树序列的方法。,