回路矩阵与割集矩阵.ppt

1，图论，(v )，刘晓华，2，3.4回路矩阵和分割矩阵中有方向连通图G=(V，e )的回路矩阵和分割矩阵，与g的支持树有密切的关系。 电路矩阵及其性质(1)概念t是具有连通图g的支持树，对于不在t上的边e，T e包含唯一的电路c。 对电路c给定参照方向时，c中方向与电路方向一致的边称为正方向边，否则称为反方向边，与3g的所有一次电路对应的向量构成一个矩阵。 这就是g的完全电路矩阵Ce。 令g的所有边为e1、e2、em，则主电路Ci对应于向量(ci1、ci2、cim )，在这些向量中，4、例(p.46 )为右图的完整电路矩阵. 5，一个图的主电路较多，且其中最基本的是什么？ 或者，如果将定义了Ce的哪一行构成所有行的非常无关的组的t作为图g的1根支撑树，则与t以外的各边对应的电路(1边恰好与1个电路对应，电路的方向规定其边的方向)称为基本电路，由所有的m-n 1个基本电路构成的矩阵Cf 支撑树t的馀边：T以外的任一边、6、例(p.46 )对于图g的支撑树T=e1，e5，e6，求出基本电路矩阵。 由于t的边缘e2、e3、e4分别对应于电路C1、C2、C3，因此通过重新排列行和列的顺序(相当于对各电路和各边重新编号)，能够得到包含m-n 1次单位矩阵(对应于t以外的各边)的新的基本电路矩阵，新的矩阵的秩不变。 8、(2)基本电路矩阵和完全电路矩阵的秩定理1有向图的基本电路矩阵秩为m-n 1.证明：如果将Cf作为与支持树t对应的基本电路矩阵，则t的一边只出现在对应的基本电路中，而不出现在其他基本电路中。 换句话说，在所有边缘都由矩阵Cf中的对应列构成的子阵列中，每行包含一个，所有其馀元素均为0。 Cf是m-n 1行，但因此证明该行向量组没有线性，其秩为m-n 1。 另外，定理2有向图g的关联矩阵b和完全电路矩阵Ce的边的顺序一致时，有BCeT=0。对b的第I个行为(bi1、bi2、bim )、Ce的第j个行为(Cj1、cj2、cjm )进行设置，则BCeT的第I行第j个元素是dij=bij1bi2jaj2bicjm.b的第I行对应节点vi、Ce的第j行对应电路cj 如果Cj不通过vi，则对于满足bik0的k，dij=0，因为cjk=0； 当Cj通过vi时，若Cj两边ek、el通过vi，则dij=bikcjkbilcjl=11 1(-1)=0.10，定理3连通图g的完全电路矩阵Ce的等级为m-n 1.基本电路矩阵Cf为完全电路矩阵的Ce的子阵列， 在秩(Ce)=m-n1.sylvester的定理中，如果AnmDms=0，则秩(a )的秩(D)=m .定理1和定理2，BCeT=0，秩(B)=n-1，根据秩(b )的秩(ce)=m，(m为边数) 11、(3)电路矩阵定义由连通图g的m-n 1个相互独立的电路构成的矩阵，称为g的电路矩阵，记为c。 性质：(1)基本电路矩阵Cf是电路矩阵。 (2)BCT=0(B和c中边的顺序一致) (3)C=PCf，p是某全秩矩阵。 (在c和Cf中边的顺序一致)，12，g的馀数树和电路矩阵的关系定理4连通图g的电路矩阵c的任意m-n 1次子矩阵行列式不是零，这些列对应于有g的馀数树(如果删除这些列的对应的边，则得到的图为1根树)。 证明：有充分性. g的支持树t知道与此子阵列对应的所有边都是t以外的所有边。 因此，在t的基本电路矩阵中，与这些边对应的各列适当地重新排列顺序而成为m-n 1次单位矩阵，因此该子矩阵的行列式不为0。 13、必要性.若将该m-n 1列置换为开头(通过改变双面编号)，则C=(C11、C12 )。 现在只是证明C12对应g的一棵支撑树。 如果C12的对应边不是树形的，则必须包括一次电路，因此必须包括一次电路。 即，有一个一次电路c，全部由C12的一部分列中对应的边构成。 因此，在电路矩阵c的第一列m-n 1(即，c1)中，由于与主电路c对应的行都是0，因此det(C11)=0，这与问题一致。另外，当知道基本相关矩阵Bk并求出基本电路矩阵Cf的定理5时，知道有向图的基本相关矩阵Bk=(B11，b1-2)，在其中，如果b1- 2不是特异的矩阵，则得到基本电路矩阵Cf=(IC12 )，其中，C12=-B11TB12-1T .在此，Cf表示Bk周边的顺序：从定理4得知B11是g的一个馀数树，即B12各列对应于一个支撑树t。 因此，对于对应于t的、由基本电路矩阵Cf的前m-n 1列构成的子矩阵，每一行包含一个，其馀元素为0。 重新排列每一行的次序(即，对每一个基本电路重新编号)、15，前m-n 1维子矩阵可为单位矩阵I。 因此，能够设为Cf=(IC12 )。 从定理2可以知道BkCfT=0，即，16，例如图3.11的基本相关矩阵，但是在这些矩阵中对应于e1，e5，e6的子矩阵不是零，Cf .17，18，2 .分割矩阵及其性质(1) -定义s是有向图G=(V，e )周围的子集，并且如果1，g=(v，e )周围的子集E-S )比g的连通分支数多1 (除了该s所包含的边的集合，图g正好有一个分支).2，对于任意的ss，g和g=(2)，有向切换组的方向(任意规定的一个方向)，19，例如S1=e2，e3，e4和S2=e4，e5切换另外，20，(2)完全划分集矩阵有由图g的完全划分集构成的矩阵，被称为完全划分集矩阵，其被标记为Se，并且其元素的定义： Sij=1，ej在Si中方向匹配的Sij=-1，ej在Si中，方向相反的Sij=0，以及21，22，(3)基本划分集对应ei存在g的分割集Si，Si只包含枝边ei和几个馀枝，与ei的方向一致。 此时将Si称为g的对应树t的一个基本剪辑。 切断Si的方向为ei的方向。 23、定义给出有向图的1棵树t时，由所有的基本分割集构成的矩阵是基本分割矩阵，记作Sf . 对应的基本分割矩阵Sf根据支撑树t而不同。 24、调整树T=e2，e3，E4，25，Sf中边的排列顺序：将t的边置于最前面，将t以外的边置于后面的t的边适当排列，对应的矩阵块可以作为1单位矩阵I。 另外，注意，如果分割矩阵与性质定理1到连通图g的完全电路矩阵Ce和完全分割矩阵Se的边缘顺序一致，则SeCet=0.证明存在Se的第I行为(Si1、si2、sim )、Ce的第j行为(cq1、cj2、cjm )， 对于SeCeT的第I行第j个元素，如果由于dij=si1j2j2simcjm.se的第I行对应于分配集合si，并且因此Cj和si不交叉，则对于Sj所穿过的边ek(Cj不穿过)，sikcjk=10=0； 在Cj通过的边ek(Sj不通过)上，sikcjk=01=0； 因此，dij=0.27、Cj与Sj相交时，有偶数条共同的边。 一半的边与切割方向相同，另一半的边与切割方向相反。 在Sj通过但Cj不通过的边ek中，有sikcjk=10=0。 Sj和Cj通过的一对边ek， 在ek (与切割方向相同，与切割方向相反)上，由于sikcjksikcjk=11 (-1 )=0，因此dij=0.28定理2连通图g的完全分割集矩阵Se的秩为n-1 .定理3连通图g的分割集矩阵s的任一个n-1次子矩阵矩阵行列式不为零， 只有与这些列为g的树(类似于电路矩阵)对应的定理4，Sf和Cf分别连通图g的树t的基本分割集合和基本电路矩阵，边的顺序一致。 Sf=(Sf11，I )，Cf=(I，Cf12 )，Sf11=-Cf12T。 (可从SeCeT=0得到)，29，3.5支持树的生成(1)两树的距离：将t1，t2作为连通图g的2根生成树。 如果在t1中k条边不属于t2，则称为t1和t2的距离d(t1，t2)=k。 如果d(t1，t2)=k，则d(t2，t1)=k .基本树变换部：将t1设为连通图g的一个生成树，如果对边et1、边et1、t 1加上边e、边e，则g的新生成树t2=t1(e，e )。 在基本树变换中，从t1到t2的距离为1.30，基本剪辑Se(t0):对于连通图g的一条生成树t0、t0的一边e，与基本剪辑Se(t0)相对应，因此树t0具有与n-1个基本剪辑对应的BSE (t1) (b1)相反，如果t1-e b是一棵树，et1，be则是bSe(t1)。 另外，对于定理2g的一条生成树t0、et0，如果Se(t0)=e、b1、b2、bp，则t0-e b1、t0-e b2、t0-e bp不包含e，是距t0的距离为1的g的所有生成树。 因此，g中距离为1的全部树由t1=e4，e2，e3、t2=e6，e2，e3、t3=e1，e5，e3、t4=e1，e6，e3、t5=e1，e2，e4、t6=e1，e2，e 5，33、(3)g的生成树t0， 对于et0，在成为Te=t0-e b:bSe(t0)的be、(不包括e且距t0的距离为1的g的全部生成树)上的例子中，将Te1=t1、t2、Te2=t3、t4、Te3=t5、t6 .定理t0=(e1、e2、ek )设为g中的1根生成树对于34、g的生成树t0和t0的边e和f，分别由Tef=t0-f b:bSf(t0)Sf(t )，tTe，BF，(e， 不包含f，对于距t0的距离为2的g的全部生成树)，即树t0中的一边e，将e置