《非连通图的结点和弧经适当排列可得到为对角分块阵的关联矩阵.ppt》由会员分享，可在线阅读，更多相关《非连通图的结点和弧经适当排列可得到为对角分块阵的关联矩阵.ppt（49页珍藏版）》请在三一办公上搜索。
1、割边 图 G=(V,E)中，eE。设 G=(V,Ee)，若G 的连通分支数目比G多1，则称e为G的一条割边。定理3-1-1 上述e、G中，e是G的一条割边当且仅当e不属于G中任何回路。树 连通图G=(V,E)，若G中不含任何回路，则称G为树。|V|=1时称之为平凡树。,3.1 树的基本概念,定理3-1-2 T=(V,E)是结点数 n=|V|1 的树，则下述命题等价：T是无回路的连通图；T是连通的，且有n1条边；T有n1条边，且T中无回路；T是连通的，且T中的每一条边都是割边；T的任意两点间有且只有唯一的通路；T中无回路，但若在T的任一对不相邻的顶点之间增加一条边，则构成T中的唯一回路。,3.1
2、 树的基本概念,证明,上述定理内容也可作为树的等价定义。推论1 任一非平凡树至少有两个结点的度为1。推论2 G是一棵树当且仅当G是最小连通的（从G中去除任意一边即破坏了G的连通性）。,3.1 树的基本概念,生成树 G=（V，E），若G的一个生成子图是一棵树，则称之为G的一棵生成树（记为T）。G中在T中的边称为（关于T的）树枝，G中不在T中的边称为（关于T的）弦。G中的所有结点和弦构成的子图称为（关于T的）余树。余树不一定是树。,3.1 树的基本概念,定理3-1-3 任何连通图至少有一棵生成树。证明 破圈法构造推论1 设G=（V，E）连通，则|E|V|1。,3.1 树的基本概念,关联矩阵 G=（
3、V，A）中，设V=v1,v2,vn，A=a1,a2,am，令 B=(bij)nm，其中 1 aj=A bij=1 aj=A 0 其它 称B为G的关联矩阵。,3.2 关联矩阵,例,3.2 关联矩阵,关联矩阵的特征：每列有两个非零元+1、1；孤立点对应的行为0向量；非连通图的结点和弧经适当排列，可得到为对角分块阵的关联矩阵。,3.2 关联矩阵,定理3-2-1 连通图 G=(V,A)的关联矩阵B的秩 r(B)|V|。证明 设n=|V|。B的n列行向量之和为0，故 r(B)n。,3.2 关联矩阵,定理3-2-2 图G的关联矩阵B中任一k阶方阵的行列式值为0、+1或-1。证明 设Bk为B中任一k阶方阵，
4、kn=|V|，km=|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 关联矩阵,证明(续)i=i-1，若 i 2 转；否则计算结束，此时 det(Bk)=det(B2)或 det(Bk)=-det(B2)，易知 B2的值只能为0、+1或-1。,3.2 关联矩阵,定理3-2-3 连通图 G=(V,A)的关联矩阵B的秩 r(B)=n-1，n=|V|。证明
5、先证明 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 不妨设 kj0(j=1,2,l，l n-1)，ks=0(l s n-1)，则有：k1V1+k2V2+klVl=0,3.2 关联矩阵,（续）由于B中每列只含一个+1和一个-1，欲使上式成立，由行向量 V1,V2,Vl 构成的矩阵的每列必须同含+1和-1元，或只含0元。例如，假如 p 列（0p m,m=|A|）只含一个+1元，该元所在行为 t 行(0t l)，则有：k10+k20
6、+kt-10+kt1+kt+10+kl0=0 此时必须 kt=0(t l)，矛盾。,3.2 关联矩阵,（续）作适当列交换，得：,其中C式每列同含+1和-1。故原关联矩阵B 经过上述列交换可得分块矩阵如图所示，其中l n-1。此时 G 非连通，矛盾。故 r(B)n-1 又由定理3-2-1，r(B)n 所以 r(B)=n-1,3.2 关联矩阵,基本关联矩阵 从连通图 G=(V,A)的关联矩阵Bnm中去掉与结点vkV对应的一行，得到一个(n-1)m 的矩阵Bk，称为对应于结点vk的基本关联矩阵。定理3-2-4 若Bk是连通图 G=(V,A)的基本关联矩阵，C=a1,a2,al（aiA,i=1l）构成
7、G中的某条回路，则C的各边对应的Bk的各列向量线性相关。证明（下页）,3.2 关联矩阵,证明 设B、Bk中与C各边对应的列向量分别构成矩阵 Dnl、Dk(n1)l。C最多经过 l 个结点，故D中最多有 l 个非0行向量。经过适当重排行序后得到D和Dk形如：,3.2 关联矩阵,若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。
8、综上，r(D1k)l，即D1k中的列向量线性相关，故D中的列向量也线性相关，定理得证。定理3-2-4 揭示了图的回路与基本关联矩阵之间存在着内在联系。,3.2 关联矩阵,定理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 关联矩阵,定理3-3-1(Binet-Cauchy)已知A=(aij)mn，B=(b
9、ij)nm，且 mn，则：,其中，Aj 是从A中取第 j1,j2 jm(1 j1 j2 jm n)列组成的行列式，Bj 是从B中取第 j1,j2 jm 行组成的行列式，是对所有满足 1 j1 j2 jm n 的排列（j1,j,jm）求和。证明（略）,3.3 生成树的数目,例,3.3 生成树的数目,定理3-3-2 设连通图G的基本关联矩阵 Bk，则G的生成树的数目为 det(BkBkT)证明 由Binet-Cauchy定理有：,Bj为Bk的某(n-1)阶子式。由定理3-2-5，当且仅当Bj各列对应的弧构成一棵生成树时，Bj 0；又由定理3-2-2，此时 Bj2=1。而(j)是在图G中任取n1条边
10、的所有可能性。,3.3 生成树的数目,算法(求所有生成树清单)设连通图 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 生成树的数目,例 图的关联矩阵 B,3.3 生成树的数目,取：,则：,由定理3-3-2，图的生成数的数目是：det(B4 B4T)=16,3.3 生成树的数目,又取：,则：,3.3 生成树的数目,作行列式展开得：,3.3 生成树的数目,有向树 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图
11、为一棵有向树，记为T。外向树 一棵有向树T，若其中有且仅有一个结点v0的负度为0，其余结点的负度为1，则称T是一棵以v0为始点的外向树，或叫以v0为根的有根树。其中正度为0的结点称为有根树的叶子。定义 对有向树 T=(V,A)，若 u,vV且 A，则称 u为v的父亲，v为u的儿子。若从u到v存在有向道路，则称u是v的祖先，v是u的后代（子孙）。,3.4 有向树,树的高度 设有根树 T=(V,A)，v0为树根。u V的深度是从v0 开始到达u的有向路的长度，T的高度是从v到T的叶子的最长路的长度。根结点深度为0，称为第0层；深度同为i 的结点构成树的第i 层；具有最大深度的结点的深度称为树的深度
12、（高度）。,3.4 有向树,有序树 将各树的每个结点的所有儿子按次序排列，称这样的根树为有根有序树。有序树的每个结点的出度小于或等于m时，称为m元有序树。有序树的每个结点的出度只为 0或 m 时，称为m元正则有序树。,3.4 有向树,例 语法树,3.4 有向树,例 判定树：有8个硬币，已知其中有7个真币，一个假币。假币的重量与真币不同。请使用一个天平判定哪个是假币。,3.4 有向树,3.4 有向树,二元树 二元树是2元有序树（各结点的出度不大于2）二元树的任一结点只可能具备四种形态之一：,3.5 二元树,满二元树 高度为k的二元树，除k层外其他各层结点均有形态（）。编号二元树 高度为k的满二元
13、树，对其结点按从上到下，同层结点从左到右的原则编号，得到结点从12k+1-1 的编号序列。得到上述结点编号的二元树称为编号二元树。完全二元树 具有n个结点的二元树，若其构造与具有不少于n个结点的编号二元树的前n个结点的构造相同，则称之为一棵完全二元树。,3.5 二元树,高度为k的完全二元树，其k-1层以上结点构成一棵高度为k-1 的满二元树。理想二元树 高度为k的理想二元树，其k-1层以上结点构成一棵高度为k-1 的满二元树。正则二元树 每个结点的出度为 0或者2的二元树称为一棵正则二元树（二元正则有序树）。,3.5 二元树,二元树的性质第i 层的结点数最多为2i；深度为k的二元树最多有2k+
14、1-1个结点；记二元树出度为2的结点数目为n2，叶子数目为n0，则有：n0=n2+1多元树与二元树的对应关系：以结点的最左儿子为对应二元树中该结点的左儿子；以结点的右兄弟为对应二元树中该结点的右儿子。,3.5 二元树,定义 给具有k个叶子结点的二元树的各个叶子分别赋以非负实数权 pi(i=1,2,k)，并设对应的各个叶子的深度分别为 li(i=1,2,k)，则称,为该树的带权外部通路总长。最优二元树 具有k 个叶子结点且各个叶子分别被赋以非负实数权 pi(i=1,2,k)的二元树中，具有最小带权外部通路总长者称为相对于pi(i=1,2,k)的最优二元树。,3.6 Huffman树,Huffma
15、n 算法 给定k个非负实数，构造以它们为叶子带权且具有最小M(T)的最优二元树。i k；若 i=1 结束；将 i 个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，构造其父亲结点，并以此左右儿子的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。i i-1，转(2)。,3.6 Huffman树,Huffman树 由Huffman算法构造的二元树称为相对于非负实数权 pi(i=1,2,k)的Huffman树。定理3-6-1 Huffman树是一棵相对于非负实数权 pi(i=1,2,k)的最优二元树。,3.6 Huffman树,p1+p2,
16、p1,p2,3.6 Huffman树,证明 设非负实数权 p1,p2,p3,pk 且 p1 p2 p3 pk。只须证明带权 p1+p2,p3,pk 的一棵最优二元树，经过下列转换后可得一棵带权 p1,p2,p3,pk 的最优二元树。,3.6 Huffman树,非递减非负实数权序列 p1,p2,p3,pk 构成的一棵最优二元树中，p1,p2 必是一对兄弟。证明：若p1没有兄弟，将其与其父亲结点重叠，可得到一棵符合条件的M(T)更小的二元树，矛盾。在具有最小M(T)的二元树中，权值最小的结点必在最底层，故p1的兄弟只能是p2（或与p2相等者）,设上述 p1,p2,pk 的一棵最优二元树 T 如下：
17、,3.6 Huffman树,设T中 p1,p2 路径长度均为d，则 M(T)=M(TA)+p1d+p2d,构造T1 如图（此时 还不能肯定T1是一棵最优二元树）,则 M(T1)=M(TA)+(p1+p2)(d-1)故 M(T1)=M(T)p1 p2,设带权 p1+p2,p3,pk（不一定非递减）的一棵最优二元树为T1 如图，并构造带权 p1,p2,p3,pk 的二元树T（同样此时不能肯定T 是一棵最优二元树）。,TB,3.6 Huffman树,显然有 M(T1)=M(T)p1 p2 注意到T1 为带权p1+p2,p3,pk 的一棵最优二元树，即：M(T1)M(T1)所以：M(T)p1 p2 M
18、(T)p1 p2 或：M(T)M(T)注意到T为带权 p1,p2,p3,pk 的一棵最优二元树，故T也是一棵带权 p1,p2,p3,pk 的最优二元树。至此，问题归结为求带权 p1+p2,p3,pk 的最优二元树。,3.6 Huffman树,Huffman树是一棵正则二元树。前缀码设 a1 a2 an-1 an 为长为n的符号串，称其子串a1,a1 a2,a1 a2 an-1分别为该符号串的长度为1,2,n-1的前缀。设有符号串集合 A=1,2,m，若其中对任意的 I,j A，ij，有i j 且互不为前缀，则称A是一个前缀码。二元前缀码前缀码A=1,2,m 中的i 只由两种符号（如0、1）组成
19、时，称A为一个二元前缀码。,3.6 Huffman树,定理3-6-2 对任意一棵正则二元树的叶子，都存在唯一的一个二元前缀码。例 P.314 图16-10,3.6 Huffman树,Huffman编码 以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子的Huffman树，得到关于源码符号集的一个二元前缀码，称为其Huffman编码。定理3-6-3 Huffman编码是关于该源码符号集的最短二元前缀码。证明 一段长度为N的源码电文，经过上述Huffman编码译码后的译文长度为 M(T)*N，而Huffman树是一棵最优二元树，具有最小的M(T)值。,3.6 Huffman树,实现译文长度最短的二元前缀码设计过程：字频统计等概率假设Huffman树构造Huffman编码方案确定例 设一段电文含有a,b,c,d,e,f,g共7个字符，它们的字频分别是：a:35%b:20%c:15%d:10 e:10%f:5%g:5%。试为这7个字符设计一套最短二元前缀编码方案。,3.6 Huffman树,二元树的遍历：先序、中序和后序遍历二元树。二元树的应用：二叉排序树二元树的应用：算术表达式的波兰式和逆波兰式。m元树的遍历：深度优先、广度优先遍历。图的遍历：深度优先、广度优先遍历。,3.7 树与图的遍历,
