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

3.2基本关联矩阵基本关联矩阵及其性质及其性质一、一、树树：连通、无回路、每边是割边、：连通、无回路、每边是割边、n-1条边条边二、至少有两个度数为二、至少有两个度数为1的结点的结点(叶子叶子)三、矩阵线性无关三、矩阵线性无关最大行数最大行数=矩阵线性无关矩阵线性无关最大列数最大列数=矩阵矩阵中非零的方阵中非零的方阵的最大的最大阶数阶数=列对应图中边，最大线性无关的列对应图中边，最大线性无关的边数边数四、回路中的边线性四、回路中的边线性k相关相关，对应的列线性相关，对应的列线性相关，这些列中任意这些列中任意K阶子式为阶子式为0本本节讨论对象为节讨论对象为有向连通图有向连通图G G定义基本关联矩阵定义基本关联矩阵:在在有向有向连通图连通图G的的关联矩阵关联矩阵B中划去任意结点中划去任意结点Vk所对应所对应的行的行,得到一个得到一个(n-1)m的矩阵的矩阵Bk,称称为为G的一个的一个基本关联矩阵基本关联矩阵.V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10有向图有向图G的关联矩阵的关联矩阵B的秩的秩n证明证明 由于矩阵由于矩阵B的的每列每列表示表示每边每边的起点与的起点与终点终点,起点起点处为处为1,终点终点为为-1.行行1+行行2+行行n=0,故故 行行n=-行行1-行行2-行行n-1，即行，即行n为前为前n-1的线性组合，即行的线性组合，即行n与前与前n-1行行不独立不独立,故故独立行数独立行数即即B的秩的秩n.设设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设设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.定理定理 连通图连通图G有有n个结点，点与边的完全个结点，点与边的完全关联矩阵的秩为关联矩阵的秩为n-1。证明：证明：线性线性无关无关的的最大行最大行数为数为n-1，再多，再多1行即行即n行就相关，即行就相关，即线性线性相关相关的的最少行最少行数为数为n，用用反证法反证法证明。证明。即假设即假设线性相关线性相关的最少的最少行数为行数为Ln，寻寻找错误的结论。找错误的结论。定理定理 连通图连通图G有有n个结点，点与边的完全个结点，点与边的完全关联矩阵的秩为关联矩阵的秩为n-1。证证:假设假设线性相关线性相关的最少的最少行数为行数为Ln.k1b(i1)+k2b(i2)+k Lb(iL)=0 ki 0,i=1L 因因关联矩阵关联矩阵每列只有二个非每列只有二个非0元，则元，则这这L行行所形所形成的成的矩阵中矩阵中每列每列至多至多有有2个非个非0元，有些列可能全元，有些列可能全是是0，但不可能只有但不可能只有1个非个非0元元。假设假设某列某列j只有只有1个非个非0元在元在ki行，则该列各数的行，则该列各数的线性组合线性组合=ki*bij=ki=0，与，与ki 0矛盾矛盾.对关联矩阵对关联矩阵的列的列进行调整，将这进行调整，将这L行行中列中含中列中含有有2个非个非0元元的列调整最前面，全的列调整最前面，全0的调整到后面的调整到后面.最后将这最后将这L行行调整到最前面。调整到最前面。定理定理 连通图连通图G有有n个结点，点与边的完全个结点，点与边的完全关联矩阵的秩为关联矩阵的秩为n-1。证证:假设假设线性相关线性相关的最少的最少行数为行数为Ln.对关联矩阵的列进行调整，将这对关联矩阵的列进行调整，将这L行中列中含行中列中含有有2个非个非0元元的列调整最前面，全的列调整最前面，全0的调整到后面的调整到后面.最后将这最后将这L行调整到最前面。行调整到最前面。记记L行中含行中含2个非个非0元元的的列数为列数为t，即这，即这L行只与行只与这这t条边条边相关，则有如下分块矩阵：相关，则有如下分块矩阵：2个非个非0元元的列的列全全0元元的列的列定理定理定理定理3.2.3 3.2.3 连通图连通图连通图连通图GG有有有有n n个结点个结点个结点个结点，关联矩阵的秩为，关联矩阵的秩为，关联矩阵的秩为，关联矩阵的秩为n-1n-1。证证:假设假设线性相关线性相关的最少的最少行数为行数为Ln.L行对应的行对应的L点只与这点只与这t条边相关，条边相关，n-L个点与个点与t条没关系，条没关系，那么那么n-L个点不可能与个点不可能与L点有边相连！故不连通！点有边相连！故不连通！因因L0，则，则B至少分为两个连通分枝，而至少分为两个连通分枝，而B仅仅是是B进行进行“行行-行行”与与“列列-列列”互换得到互换得到,是改变点与是改变点与边在关联矩阵中出现的顺序，故保持连接性不变，故边在关联矩阵中出现的顺序，故保持连接性不变，故B也有也有2个连通分枝，故原图个连通分枝，故原图G不连接不连接.与原图是与原图是连通矛盾连通矛盾！故线性相关至少需要故线性相关至少需要n行，小于行，小于n无关，线性无关最大无关，线性无关最大行数为行数为n-12个非个非0元元的列的列全全0元元的列的列 定理定理 连通图连通图基本关联基本关联矩阵矩阵Bk的秩的秩n-1.证明证明:由定理的证明可知由定理的证明可知,线性相关线性相关的行数的行数至至少为少为n，故，故小于小于n则则线性无关线性无关。即任意即任意n-1行肯定行肯定线性无关线性无关，而，而Bk是关联矩阵是关联矩阵的某的某n-1行，故线性无关，故行，故线性无关，故Bk的秩为的秩为n-1。说明说明：若若G的的结点为结点为n，连通，连通分支数为分支数为w，则，则完全关联完全关联矩阵矩阵的秩为的秩为n-w。分支数分支数w=点数点数n-关联矩阵的秩关联矩阵的秩rank(B)特别是特别是w=1即即G连通时连通时,秩为秩为n-1 点数是确定的，关联矩阵随网络连接情况而变点数是确定的，关联矩阵随网络连接情况而变化，故根据其秩数可判断网络的连通性。化，故根据其秩数可判断网络的连通性。推论推论 n个结点树个结点树T的的基本关联基本关联矩阵的秩是矩阵的秩是n-1.证明证明:T是是连通无回路连通无回路的图，是一个特殊的图，是一个特殊的连通图。的连通图。给给每条边每条边加上方向，加上方向，父结点父结点为边的起点，为边的起点，子结点为边的终点，则树子结点为边的终点，则树T是有是有向连通图向连通图。根据根据定理定理可知，故它的可知，故它的基本关联矩阵基本关联矩阵的的秩是秩是n-1.有向图的连通性有向图的连通性,是在忽略每边的方向是在忽略每边的方向后确定的后确定的,这与其它教材上关于有向图的这与其它教材上关于有向图的定义定义不一样不一样,请注意请注意.结点数为结点数为n的连通图的连通图G的的基本关联矩阵基本关联矩阵的的秩是秩是n-1,其中边数最少的连通图是其中边数最少的连通图是“树树”,它恰好有它恰好有n-1边边,这这n-1边是线性无关边是线性无关的的.其它连通图其它连通图中的边数中的边数n-1,而这些边中又而这些边中又只有只有n-1列是列是线性无关线性无关的的,那么哪些列是那么哪些列是线性无关线性无关的呢的呢?如何寻找如何寻找呢？呢？定理定理 C是连通图是连通图G的一个的一个回路回路,Bk是是G的一个的一个基基本关联矩阵本关联矩阵,那么回路那么回路C中各点与中各点与各边对应各边对应Bk的的列列线性相关线性相关.一个回路中的边是线性相关的一个回路中的边是线性相关的。回路矩阵能找出所有相关、无关边回路矩阵能找出所有相关、无关边 设初级设初级回路回路C包含了包含了G的的L个结点个结点，由点与边均，由点与边均不重复，不重复，C肯定肯定有有L条边条边,这这L条边对应关联矩阵条边对应关联矩阵B的的L列列,这这L列构成列构成B的子阵的子阵B(Gc)，环，环C本身的关本身的关联矩阵联矩阵B(C)(L点点L边边)。V1V2V3V4V5V6e2e1e3e4e5e6e7e8e9e10子阵子阵B(Gc)B(C)(L点点L边边)证明证明:只需针对只需针对初级回路初级回路进行讨论进行讨论.设回路设回路C包含了包含了G的的L个结点个结点L条边条边.不妨假设不妨假设Ln,这这L条边对应关联矩阵条边对应关联矩阵B的的L列列,这这L列构成列构成B的子阵的子阵B(Gc)B(Gc).回路回路C的关联矩阵的关联矩阵B(C)B(C)是是L阶方阵阶方阵,又由于又由于C是连通图是连通图,故故B(C)B(C)的秩为的秩为L-1.由秩的定义可知，矩阵由秩的定义可知，矩阵B(C)的的L个列向量个列向量线性相关。线性相关。而基本关联矩阵而基本关联矩阵Bk中与这中与这L条边对应的条边对应的L列向量的下方列向量的下方(即即n-L-1行行)全是全是0(因这因这L条边只与回路条边只与回路C中的中的L个结点相个结点相关关,与其他点无关故为与其他点无关故为0)，故，故Bk中这中这L个列也线性相关。个列也线性相关。子阵子阵B(Gc)B(Gc)的的的的L L列相关列相关列相关列相关B(C)(B(C)(L L点点点点L L边边边边)秩为秩为秩为秩为L-1,L-1,则其则其则其则其L L列相关列相关列相关列相关 推论推论 设设H是连通图是连通图G的的子图子图,若若H含含有回路有回路,则则H的诸边对应的的诸边对应的G的基本关的基本关联矩阵联矩阵各列线性相关各列线性相关.减少找回路范围减少找回路范围定理定理 令令Bk是有向连通图是有向连通图G的的基本关联基本关联矩阵矩阵,Bk的某的某n-1阶子阵行列式阶子阵行列式非非0其各列对应的边构成其各列对应的边构成一棵支撑树一棵支撑树。不在某回路上不在某回路上!定理定理 令令Bk是有向是有向连通图连通图G的基本关联矩的基本关联矩阵阵,那么那么Bk的某的某n-1阶子阵行列式阶子阵行列式非非0的的是是其各列其各列所对应的边构成所对应的边构成G的的支撑树支撑树.证明证明:.如果某个如果某个N-1阶子阵阶子阵Bk(GT)的行列式非的行列式非0,则这则这n-1列线性无关列线性无关,即这即这n-1边线性无关边线性无关。由推理可知由推理可知,则这则这n-1条边中条边中不含回路不含回路(若若有回路则线性相关有回路则线性相关)。由树的定义含有由树的定义含有n-1条不构成回路条不构成回路的边，的边，即即构成一棵树构成一棵树，即为支撑树。，即为支撑树。定理定理 令令Bk是有向是有向连通图连通图G的基本关联矩阵的基本关联矩阵,那么那么Bk的某的某n-1阶子阵行列式阶子阵行列式非非0的的是其是其各列所对应的边构成各列所对应的边构成G的的支撑树支撑树.证明证明:.设设对应边对应边的构成的构成一棵树一棵树,则由树的定义可则由树的定义可知知,它有它有n-1条边无回路条边无回路,则这些则这些边线性无关边线性无关,对应的对应的列向量线性无关列向量线性无关。基本关联矩阵基本关联矩阵Bk(T)只有只有n-1行行，因此这，因此这n-1行与树中的行与树中的n-1边所对应的列向量构成边所对应的列向量构成n-1阶阶方阵方阵。由线性代数知识可知由线性代数知识可知，线性无关的，线性无关的n-1列列所对应的所对应的n-1阶行列式阶行列式值值不等于不等于0。定理定理 令令Bk是有向是有向连通图连通图G的基本关联矩阵的基本关联矩阵,那么那么Bk的某的某n-1阶子阵行列式阶子阵行列式非非0的的是其是其各列所对应的边构成各列所对应的边构成G的的支撑树支撑树.此定理说明此定理说明，基本关联矩阵，基本关联矩阵Bk中，中，n-1阶阶非非0子式子式的的个数个数，为，为G的的生成树的棵数生成树的棵数。而而Bk恰好恰好有有n-1行行,关键关键是寻找是寻找n-1个线性个线性无关无关的列的列,构成树的边的组合是其对应子式构成树的边的组合是其对应子式非非0.下一节，将介绍基于基本关联矩阵计算下一节，将介绍基于基本关联矩阵计算生成树棵数的生成树棵数的方法、写出生成树序列的方方法、写出生成树序列的方法。法。