第三章连通度.pptVIP

最优2叉树 设2叉树T有t个树叶v1, v2, …, vt，层数分别为l1, l2, …, lt ，这些树叶分别带有权w1, w2, …, wt，称 为T的权. 在所有有t个树叶，分别带权w1, w2, …, wt的2叉树中，权最小的称为最优2叉树. Huffman算法 给定实数w1, w2, …, wt，设w1 ≤ w2 ≤…≤ wt . (1) 连接权为w1, w2的两个顶点，得一个分支点，其权为w1 + w2. (2) 在w1+w2, w3, …, wt中选出两个最小权，连接它们对应的顶点，得新分支点及所带的权. (3) 重复(2)直到形成t ?1个分支点，t个树叶. 应用：最佳前缀码与文件压缩 第三章 连通度 3.1 连通度 3.2 块 3.3 可靠通讯网络的构造 3.1 连通度 图的连通程度是有区别的 设G是图，若V 的子集V’ 使得G ?V’不连通，则称V’ 为G的顶点割. 若V’有k个元素，则称它为k顶点割. 图G所具有的k顶点割中最小的k ，称为G的连通度，记为κ(G). 完全图没有顶点割，定义它的连通度为ν ? 1. 不连通图及平凡图的连通度为0. 若κ(G)≥k ，则称G是k连通的. 设G的顶点集V被划分为S1和S2两个部分，用[S1,S2]表示一个端点在S1中，另一个端点在S2中的所有边的集合，称为G的一个边割. 若E’有k个元素，则称它为k边割. G的所有k边割中最小的k ，称为G的边连通度，记为κ’(G). 不连通图及平凡图的边连通度为0. 若κ’(G)≥k ，则称G是k边连通的. 定理3.1 κ ≤ κ’ ≤ δ. 3.2 块 没有割点的连通图称为块. K2是块，至少有3个顶点的块是2连通的. 一个图的块是该图的一个子图，这个子图本身是块，而且是有此性质的块中的极大者. G中一族路称为内部不相交的，如果任何顶点都不是两条或两条以上的路的内部顶点. 定理3.2(Whitney 1932) 一个至少含三个顶点的图是2连通的，当且仅当它的任意两个顶点至少被两条内部不相交的路所连. 推论3.2.1 若G是2连通的，则G的任意两个顶点都位于同一个圈上. 推论3.2.2 若G是2连通的，则G的任意两条边都位于同一个圈上. 同样，若G是2连通的，则G的任意一个顶点和任意一条边都位于同一个圈上. 注： 定理3.2是Menger定理的特殊情形（第11章） 图G是k连通的，当且仅当G的任意两个顶点至少被k条内部不相交的路所连. 对于边也存在一个类似的结论： 图G是k边连通的，当且仅当G的任意两个顶点至少被k条边不重的路所连. 3.3 可靠通讯网络的构造 一个图可以看成是一个通讯网络，图的连通度（边连通度）就是指至少有多少个通讯节点（多少条通讯线路）发生故障才会造成系统不连通. 显然连通度和边连通度越高，网络就越可靠. 问题：在一个赋权图中，如何确定一个有最小权的k连通子图？ k ＝1时，这就是连线问题，可用Kruskal算法求解. 当k大于1时，这个问题是非常困难的，目前还没有有效的算法. 第3章 连通度 第3章 连通度