第七章-连通性.docVIP

第七章 连通性 教学安排的说明 章节题目：§7.1 连通度和边连通度 学时分配： 2课时 本章教学目的与要求：掌握连通度和边连通度的概念；掌握两种连通度与图的最小度之间的关系. 课 堂 教 学 方 案 课程名称：§7.1 连通度和边连通度 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法 教学目的与要求：掌握连通度和边连通度的概念；掌握两种连通度与图的最小度之间的关系. 教学重点、难点：重点是点连通度与边连通度的定义；两种连通度与图的最小度之间的关系。难点是两种连通度与图的最小度之间的关系。 教学内容： 第七章 连通性 §7.1 连通度和边连通度 在我国，有多条国道主干线和其它高等级公路交汇和过境的城市(规划上称为重要结点城市)，这些公路的交汇与过境普遍存在相互之间的连通性，尤其是城市规划中主要出入口总体上的协调配合问题.在通信网络或航空网中的应用中，系统不能太“脆弱”，但出于费用的考虑，也不是系统越稳定越好。不可能任何两个城市之间都有道路相连，也不可能任何两个通讯站点之间都相连。用图论的语言描述，这些图既要保持很好的连通性，也不必要边数太多。要妥善处理好这类问题，需要如何衡量一个图的连通程度，需要从点和边两个角度考虑，为了讨论这一点，本章引入割集和连通度的概念、我们的讨论限于简单无向图。 （一）、割点，割边，点割集和边割集 图区分为连通图和分离图两大类。每个分离图由若干个连通分支构成。连通图经删除某些顶点或边之后可能变成分离图。 所谓从图G中删除顶点子集V1，是指删除V1中每一个点且同时删除图G中所有与V1中点相关联的边，剩下的子图记为G-V1，这里V1是G的顶点集V的一个非空真子集。 所谓从图G中删除边的子集E1是指删除E1中每一条边，而G中所有顶点全部保留下来。剩下的子图记为G-E1，这里E1是G的边集E的一个非空子集。 问题: 如何定量比较无向图连通性的强与弱?让我们观察下列的一组都是五个顶点的连通图。 ? ? ? ? (1) (2) (3) (4) 图1 在图（1）中删除一条边之后，子图不再连通。 在图（2）中，至少需要删除两条边之后，子图才不再连通。 在图（3）中，至少需要删除三条边之后，子图才可能不连通。 在图（4）中，删除顶点集的任何非空真子集之后，子图都连通；但删除四个顶点之后，剩下的只是一个平凡图；又至少需要删除四条边之后子图才不连通。 再看如下的一些图: ((G)=1 ((G)=1 ((H)=2 ((H)=2 ((F)=3 ((F)=3 ((K5)=4 ((K5)=4 由此可见，连通图其连通的程度是不尽相同的。“破坏连通性”指 p(G-V’)p(G), 或p(G-E’)p(G),即“变得更加不连通” 直观上看，需要删除较多的顶点之后才不连通的连通图其连通的程度要强一些。可否用为了使得连通图不连通所必须删除的最小的顶点个数来作为衡量一个连通图的连通程度的数量标准呢？对顶点如此，对边也能这样吗？为此我们先作一些准备工作，我们来给出与上述讨论有关的几个概念。首先假设G=（V，E）是连通图， 割点与割边： 如果u 是G中的一个顶点，且G-{u}不连通，则称u是G的一个割点。 如果e是G中的一条边，且G-{e}不连通，则称e是G的一条割边（cut-edges）。 点割集：设S为连通图G的顶点集V的子集，称S为G的点割集（cut-set of nodes）,如果从G中删除S中的所有顶点后得到的图不连通，但S的任何真子集均无这一特性。当点割集为单元素集合｛v｝时，v即为割点（cut-nodes）。 如：图2中的图有点割集{}，{}，是割点，而{}不是点割集。 图2 边割集：若E1是E的非空子集，G-E1不连通，但对E1的任何真子集E2都有G-E2连通，则称E1是G中一个边割集（cut-set of edges）。当边割集为单元素集合｛e｝时，v即为割边。 图2割集{}，{ }等，它没有割边。{ }不是割集。 再如下图: 点割集(G1中f是割点, G2中无割点) G1: {f},{a,e,c},{g,k,j},{b,e,f,k,h} G2: {f},{a,e,c},{g,k,j},{b,e,f,k,h} 边割集(G1中(f,g)是桥, G2中无桥) G1: {(a,f),(e,f),(d,f)}, {(f,g),(f,k),(f,j)}{(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)}, {(c,d)} G2: {(b,a),(b,e),(b