《非连通图的结点和弧经适当排列可得到为对角分块阵的关联矩阵.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的任一对不相邻的顶点之间增加一条边，则构成
2、T中的唯一回路。,3.1 树的基本概念,证明,上述定理内容也可作为树的等价定义。 推论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
3、.1 树的基本概念,关联矩阵 G=（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阶方阵的行列式
4、值为0、+1或-1。 证明 设Bk为B中任一k阶方阵，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-
5、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 不妨设 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 构成的
6、矩阵的每列必须同含+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 关联矩阵,（续）作适当列交换，得：,其中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)的关联矩阵B
7、nm中去掉与结点vkV对应的一行，得到一个 (n-1)m 的矩阵Bk，称为对应于结点vk的基本关联矩阵。 定理3-2-4 若Bk是连通图 G=(V,A)的基本关联矩阵， C= a1,a2,al（aiA, i=1l ）构成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
8、，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 关联矩阵,定理3-2-5 连通图 G=(V,A)，n=|V|，其基本关联矩阵Bk的任一(n-1)阶子式非零的充要条件是：该子式各列对应的图G的边构成G的一棵生成树。 证明
9、结合定理3-2-4：若此n-1条弧中存在回路，则回路对应于Bk中相应的列向量线性相关，此n-1条弧对应于Bk中相应的列向量也线性相关，该(n-1)阶子式为零，矛盾。 编号法（略）,3.2 关联矩阵,定理3-3-1(Binet-Cauchy) 已知A=(aij)mn，B=(bij)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 生成树的
10、数目,定理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条边的所有可能性。,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
11、(Bke BkT) 给出所有生成树的清单。,3.3 生成树的数目,例 图的关联矩阵 B,3.3 生成树的数目,取：,则：,由定理3-3-2，图的生成数的数目是： det(B4 B4T) = 16,3.3 生成树的数目,又取：,则：,3.3 生成树的数目,作行列式展开得：,3.3 生成树的数目,有向树 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为T。 外向树 一棵有向树T，若其中有且仅有一个结点v0的负度为0，其余结点的负度为1，则称T是一棵以v0为始点的外向树，或叫以v0为根的有根树。其中正度为0的结点称为有根树的叶子。 定义 对有向树 T=(V, A)，若 u ,
12、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 层； 具有最大深度的结点的深度称为树的深度（高度）。,3.4 有向树,有序树 将各树的每个结点的所有儿子按次序排列，称这样的根树为有根有序树。 有序树的每个结点的出度小于或等于m时，称为m元有序树。 有序树的每个结点的出度只为 0或 m 时，称为m元正则有序树。,3.4
13、 有向树,例 语法树,3.4 有向树,例 判定树：有8个硬币，已知其中有7个真币，一个假币。假币的重量与真币不同。请使用一个天平判定哪个是假币。,3.4 有向树,3.4 有向树,二元树 二元树是2元有序树（各结点的出度不大于2） 二元树的任一结点只可能具备四种形态之一：,3.5 二元树,满二元树 高度为k的二元树，除k层外其他各层结点均有形态（）。 编号二元树 高度为k的满二元树，对其结点按从上到下，同层结点从左到右的原则编号，得到结点从12k+1-1 的编号序列。得到上述结点编号的二元树称为编号二元树。 完全二元树 具有n个结点的二元树，若其构造与具有不少于n个结点的编号二元树的前n个结点的
14、构造相同，则称之为一棵完全二元树。,3.5 二元树,高度为k的完全二元树，其k-1层以上结点构成一棵高度为k-1 的满二元树。 理想二元树 高度为k的理想二元树，其k-1层以上结点构成一棵高度为k-1 的满二元树。 正则二元树 每个结点的出度为 0或者2的二元树称为一棵正则二元树（二元正则有序树）。,3.5 二元树,二元树的性质 第i 层的结点数最多为2i； 深度为k的二元树最多有2k+1-1个结点； 记二元树出度为2的结点数目为n2，叶子数目为n0，则有： n0=n2+1 多元树与二元树的对应关系：以结点的最左儿子为对应二元树中该结点的左儿子；以结点的右兄弟为对应二元树中该结点的右儿子。,3
15、.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树,Huffman 算法 给定k个非负实数，构造以它们为叶子带权且具有最小M(T) 的最优二元树。 i k； 若 i =1 结束； 将 i 个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，
16、构造其父亲结点，并以此左右儿子的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。 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,p1,p2,3.6 Huffman树,证明 设非负实数权 p1 , p2 , p3 , , pk 且 p1 p2 p3 pk 。只须证明带权 p1
17、+ 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 如下：,3.6 Huffman树,设T中 p1 , p2 路径长度
18、均为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
19、(T1) 所以：M(T) p1 p2 M(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 ，若其中对任意的
20、I , j A，ij，有i j 且互不为前缀，则称A是一个前缀码。 二元前缀码前缀码A=1, 2, , m 中的i 只由两种符号（如0、1）组成时，称A为一个二元前缀码。,3.6 Huffman树,定理3-6-2 对任意一棵正则二元树的叶子，都存在唯一的一个二元前缀码。 例 P.314 图16-10,3.6 Huffman树,Huffman编码 以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子的Huffman树，得到关于源码符号集的一个二元前缀码，称为其Huffman编码。 定理3-6-3 Huffman编码是关于该源码符号集的最短二元前缀码。 证明 一段长度为N的源码电文，经
21、过上述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 树与图的遍历,