非连通图的结点和弧经适当排列,可得到为对角分块阵的关联矩阵

1[割边]图G=(V,E)中，eE。设G=(V,E{e})，若G的连通分支数目比G多1，则称e为G的一条割边。[定理3-1-1]上述e、G中，e是G的一条割边当且仅当e不属于G中任何回路。[树]连通图G=(V,E)，若G中不含任何回路，则称G为树。|V|=1时称之为平凡树。3.1树的基本概念2[定理3-1-2]T=(V,E)是结点数n=|V|1的树，则下述命题等价：1)T是无回路的连通图；2)T是连通的，且有n1条边；3)T有n1条边，且T中无回路；4)T是连通的，且T中的每一条边都是割边；5)T的任意两点间有且只有唯一的通路；6)T中无回路，但若在T的任一对不相邻的顶点之间增加一条边，则构成T中的唯一回路。3.1树的基本概念3[证明]上述定理内容也可作为树的等价定义。[推论1]任一非平凡树至少有两个结点的度为1。[推论2]G是一棵树当且仅当G是最小连通的（从G中去除任意一边即破坏了G的连通性）。3.1树的基本概念4[生成树]G=（V，E），若G的一个生成子图是一棵树，则称之为G的一棵生成树（记为T）。G中在T中的边称为（关于T的）树枝，G中不在T中的边称为（关于T的）弦。G中的所有结点和弦构成的子图称为（关于T的）余树。余树不一定是树。3.1树的基本概念5[定理3-1-3]任何连通图至少有一棵生成树。[证明]破圈法构造[推论1]设G=（V，E）连通，则|E||V|1。3.1树的基本概念6[关联矩阵]G=（V，A）中，设V={v1,v2,…,vn}，A={a1,a2,…,am}，令B=(bij)nm，其中1aj=vi,vkAbij=1aj=vk,viA0其它称B为G的关联矩阵。3.2关联矩阵7123456712345671110000100101001011000010110000000100000010000000vvvvvvvaaaaaaa[例]a2a3a4a5a6a7a1v1v2v3v4v5v6v73.2关联矩阵8关联矩阵的特征：每列有两个非零元+1、1；孤立点对应的行为0向量；非连通图的结点和弧经适当排列，可得到为对角分块阵的关联矩阵。1000000kPP3.2关联矩阵9[定理3-2-1]连通图G=(V,A)的关联矩阵B的秩r(B)|V|。[证明]设n=|V|。B的n列行向量之和为0，故r(B)n。3.2关联矩阵10[定理3-2-2]图G的关联矩阵B中任一k阶方阵的行列式值为0、+1或-1。[证明]设Bk为B中任一k阶方阵，kn=|V|，km=|A|。初始化i=k。①Bi中任一列都含有+1和-1，则Bi不满秩，det(Bi)=0，计算结束，此时det(Bk)=0；②Bi中有某一列只含一个+1或-1，按此列作展开，得到一个降一阶子式det(Bi-1)，且det(Bi)=det(Bi-1)或det(Bi)=-det(Bi-1)；3.2关联矩阵11[证明](续)③i=i-1，若i2转②；否则计算结束，此时det(Bk)=det(B2)或det(Bk)=-det(B2)，易知B2的值只能为0、+1或-1。3.2关联矩阵12[定理3-2-3]连通图G=(V,A)的关联矩阵B的秩r(B)=n-1，n=|V|。[证明]先证明r(B)n-1。反证：若r(B)n-1，则在B中有n-1个行向量线性相关，不妨设此线性相关向量组为V1,V2,…,Vn-1。即存在不全为0的ki，i=1,2,…,n-1，使得k1V1+k2V2+…+kn-1Vn-1=0不妨设kj0(j=1,2,…,l，ln-1)，ks=0(lsn-1)，则有：k1V1+k2V2+…+klVl=03.2关联矩阵13（续）由于B中每列只含一个+1和一个-1，欲使上式成立，由行向量V1,V2,…,Vl构成的矩阵的每列必须同含+1和-1元，或只含0元。例如，假如p列（0pm,m=|A|）只含一个+1元，该元所在行为t行(0tl)，则有：k10+k20+…+kt-10+kt1+kt+10+…+kl0=0此时必须kt=0(tl)，矛盾。3.2关联矩阵14（续）作适当列交换，得：其中C式每列同含+1和-1。故原关联矩阵B经过上述列交换可得分块矩阵如图所示，其中ln-1。此时G非连通，矛盾。故r(B)n-1又由[定理3-2-1]，r(B)n所以r(B)=n-1V1V2:VlC0V1:VlVl+1:VnC00D3.2关联矩阵15[基本关联矩阵]从连通图G=(V,A)的关联矩阵Bnm中去掉与结点vkV对应的一行，得到一个(n-1)m的矩阵Bk，称为对应于结点vk的基本关联矩阵。[定理3-2-4]若Bk是连通图G=(V,A)的基本关联矩阵，C={a1,a2,…,al}（aiA,i=1…l）构成G中的某条回路，则C的各边对应的Bk的各列向量线性相关。[证明]（下页）3.2关联矩阵16[证明]设B、Bk中与C各边对应的列向量分别构成矩阵Dnl、Dk(n1)l。C最多经过l个结点，故D中最多有l个非0行向量。经过适当重排行序后得到D和Dk形如：D10l行n-l行lD=D1k0lk行n-1-lk行lDk=3.2关联矩阵17①若C不经过vk，则从B生成Bk时从D中划去的是全0(不在D1中)的行向量，lk=l，D1k=D1，即D1k每列都含+1和-1。故D1k不满秩，或r(D1k)l；②若C经过vk，则从B生成Bk时从D中划去了D1中的一行，此时lk=l-1，即D1k中最多有l-1个非0行向量，故r(D1k)l-1，或r(D1k)l。综上，r(D1k)l，即D1k中的列向量线性相关，故D中的列向量也线性相关，定理得证。[定理3-2-4]揭示了图的回路与基本关联矩阵之间存在着内在联系。3.2关联矩阵18[定理3-2-5]连通图G=(V,A)，n=|V|，其基本关联矩阵Bk的任一(n-1)阶子式非零的充要条件是：该子式各列对应的图G的边构成G的一棵生成树。[证明]结合[定理3-2-4]：若此n-1条弧中存在回路，则回路对应于Bk中相应的列向量线性相关，此n-1条弧对应于Bk中相应的列向量也线性相关，该(n-1)阶子式为零，矛盾。编号法（略）3.2关联矩阵19[定理3-3-1](Binet-Cauchy)已知A=(aij)mn，B=(bij)nm，且mn，则：其中，Aj是从A中取第j1,j2…jm(1j1j2…jmn)列组成的行列式，Bj是从B中取第j1,j2…jm行组成的行列式，是对所有满足1j1j2…jmn的排列（j1,j,…,jm）求和。[证明]（略）jjjABAB()det()3.3生成树的数目20[例]21121011311112211121210113011111311113ABAB,det()3.3生成树的数目21[定理3-3-2]设连通图G的基本关联矩阵Bk，则G的生成树的数目为det(BkBkT)[证明]由Binet-Cauchy定理有：2TTkkjjjjjBBBBB()()det()Bj为Bk的某(n-1)阶子式。由[定理3-2-5]，当且仅当Bj各列对应的弧构成一棵生成树时，Bj0；又由定理3-2-2，此时Bj2=1。而(j)是在图G中任取n1条边的所有可能性。3.3生成树的数目22[算法](求所有生成树清单)设连通图G=(V,A)，n=|V|，m=|A|，并设A={a1,a2,…,am}。对Bk=(bij)(n-1)m令Bke=(bije)(n-1)m其中bije=bijaj则det(BkeBkT)给出所有生成树的清单。3.3生成树的数目23[例]图的关联矩阵B1234123456111000100110010101001011vvvvaaaaaaa2a3a4a5a6a1v1v2v3v43.3生成树的数目24取：4111000100110010101B则：44311131113TBB由定理3-3-2，图的生成数的数目是：det(B4•B4T)=163.3生成树的数目25又取：1234145246000000000eaaaBaaaaaa则：12312441145424246eTaaaaaBBaaaaaaaaaa3.3生成树的数目26作行列式展开得：145444123424614122461145224eTaaaaBBaaaaaaaaaaaaaaaaaaaaa合并后得棵生成树()()()(16)det()3.3生成树的数目27[有向树]一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为T。[外向树]一棵有向树T，若其中有且仅有一个结点v0的负度为0，其余结点的负度为1，则称T是一棵以v0为始点的外向树，或叫以v0为根的有根树。其中正度为0的结点称为有根树的叶子。[定义]对有向树T=(V,A)，若u,vV且u,vA，则称u为v的父亲，v为u的儿子。若从u到v存在有向道路，则称u是v的祖先，v是u的后代（子孙）。3.4有向树28[树的高度]设有根树T=(V,A)，v0为树根。uV的深度是从v0开始到达u的有向路的长度，T的高度是从v到T的叶子的最长路的长度。根结点深度为0，称为第0层；深度同为i的结点构成树的第i层；具有最大深度的结点的深度称为树的深度（高度）。3.4有向树29[有序树]将各树的每个结点的所有儿子按次序排列，称这样的根树为有根有序树。有序树的每个结点的出度小于或等于m时，称为m元有序树。有序树的每个结点的出度只为0或m时，称为m元正则有序树。3.4有向树30[例]语法树Thebigelephantatethepeanut句子主语谓语冠形名动宾冠名Thebigelephantatethepeanut3.4有向树31[例]判定树：有8个硬币，已知其中有7个真币，一个假币。假币的重量与真币不同。请使用一个天平判定哪个是假币。3.4有向树32a+b+cd+e+fA+db+eabcaadgagaacdgghefbhgh=======3.4有向树33[二元树]二元树是2元有序树（各结点的出度不大于2）二元树的任一结点只可能具备四种形态之一：LRRL（Ⅰ）（Ⅱ）（Ⅲ）（Ⅳ）3.5二元树34[满二元树]高度为k的二元树，除k层外其他各层结点均有形态（Ⅳ）。[编号二元树]高度为k的满二元树，对其结点按从上到下，同层结点从左到右的原则编号，得到结点从1~2k+1-1的编号序列。得到上述结点编号的二元树称为编号二元树。[完全二元树]具有n个结点的二元树，若其构造与具有不少于n个结点的编号二元树的前n个结点的构造相同，则称之为一棵完全二元树。3.5二元树35高度为k的完全二元树，其k-1层以上结点构成一棵高度为k-1的满二元树。[理想二元树]高度为k的理想二元树，其k-1层以上结点构成一棵高度为k-1的满二元树。[正则二元树]每个结点的出度为0或者2的二元树称为一棵正则二元树（二元正则有序树）。3.5二元树36[二元树的性质]1)第i层的结点数最多为2i；2)深度为k的二元树最多有2k+1-1个结点；3)记二元树出度为2的结点数目为n2，叶子数目为n0，则有：n0=n2+14)多元树与二元树的对应关系：以结点的最左儿子为对应二元树中该结点的左儿子；以结点的右兄弟为对应二元树中该结点的右儿子。3.5二元树37[定义]给具有k个叶子结点的二元树的各个叶子分别赋以非负实数权pi(i=1,2,…,k)，并设对应的各个叶子的