离散数学李盘林版第6-8章.ppt

第7章小结 树：无向树的性质 根树：二叉树的性质及应用 3. 最优二元树对应的前缀码 4. 生成树 5. 最小生成树算法 在图的研究中，常常需要考虑删去与增加结点、结点集、边和边集（或弧集）的问题。 从图G=V,E中删去结点集S，是指作V-S以及从E中删去与S中的全部结点相联结的边而得到的子图，记作G-S； 从图G=V,E中删去边集（或弧集）T，是指作E-T，且T中的全部边所关联的结点仍在V中而得到的子图，记为G-T 割集与连通度 设无向图G＝V，E 为连通图，若有点集V 1 ? V ，使图 G 删除了 V 1的所有结点后，所得的子图是不连通图，而删除了 V 1的任何真子集后，所得到的子图仍是连通图，则称 V 1是 G 的一个点割集 。若某一个结点构成一个点割集，则称该结点为割点 。 图 (a) 中移去割点 s 后，成为有两个连通分支的非连通图 (b) 若 G 不是完全图，我们定义?(G)= min﹛ ?S ? ︱S是G的点割集﹜ 为图G的结点连通度，它表明产生不连通图而需要删去结点的最少数目。于是，对于分离图G， ?(G)= 0；对于存在割点的连通图G， ?(G)= 1。 思考：完全图的?(G)= ？ 设无向图G＝V，E为连通图，若有边集 E 1 ? E ，使图 G 中删除了 E 1中的所有边后得到的子图是不连通图，而删除了 E 1的任一真子集后得到的子图是连通图，则称 E 1是 G 的一个 边割集 。若某一个边构成一个边割集，则称该边为 割边 ( 或 桥 ) 。 ?与点连通度相似，我们定义非平凡图 G 的 边连通度 为：λ (G) ＝ min{ ∣E 1∣ | E 1是 G 的边割集 } ，边连通度λ (G) 是为了产生一个不连通图需要删去的边的最少数目。对平凡图 G 可定义λ (G) ＝ 0 ，此外一个不连通图也有λ (G) ＝ 0 。 下面是由惠特尼(H.Whitney)于1932年得到的关于结点连通度、边连通度和最小度的不等式联系的定理：对于任何一个无向图G， ?(G)≤?(G)≤δ(G)。 证明 若 G 不连通， 则k(G)＝λ(G)＝0，故上式成立。 ?? ?? 若 G 连通， ?? ??1) 证明λ(G)≤δ(G) ?? ??如果 G 是平凡图，则 λ(G)＝0≤δ(G)，若G是非平凡图，则因每一结点的所有关联边必含一个边割集，故λ(G)≤δ(G) 。 2) 再证 k(G)≤λ(G) ??(a) 设λ(G)＝1，即G有一割边，显然这时k(G)＝1，上式成立。 ??(b) 设λ(G)≥2，则必可删去某λ(G)条边，使G不连通，而删去其中λ(G)-1条边，它仍是连通的，且有一条桥e＝(u，v)。对λ(G)-1条边中的 每一条边都选取一个不同于u，v的端点，把这些端点删去，则必至少删去λ(G)-1条边。若这样产生的图是不连通的，则 k(G)≤λ(G)-1＜λ(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v，就必产生一个不连通图，故 k(G)≤λ(G)。 ?? ??由 1) 和 2) 得 k(G)≤λ(G)≤δ(G) k(G)＝2，λ(G)＝3，δ(G)＝4 例 v e G G′ e是G′的割边 ?(G′)=1 ?(G′)=1 ?(G) =2 V是G的割点 ?(G)=1 ?(G)=2 ?(G) =2 ?? ?定理 一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v ? 证明 若结点v是连通图G＝V，E的一个割点，设删去v得到子图G′，则G′ 至少包含两个连通分支。设其为 G1＝V1，El，G2＝V2，E2，任取u∈ V1 ，w∈V2，因为G是连通的，故在G中必有一条连结u和w的路C，但u和w在G′中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v。 ?? ??反之，若连接图G中某两个结点的每一条路都通过v，删去v得到子图G′，在G′中这两个结点必然不连通，故v是图G的割点。 (2)有向图的连通性 有向图G是弱连通的：忽略G的每条边的方向得到的无向图是连通图。 有向图G是单向连通的：对G的任两个顶点u，v，或有u到v的通路，或有v到u的通路。 有向图G是强连通的：对G的任两个顶点u，v，既有u到v的通路，又有v到u的通路。 例 单向连通的 不是强连通的 弱连通的 不是单向连通的 强连通的 在简单有向图中，具有强连通性质的最大子图，称为强分图 ；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图 。 在图 (a)中，由{v1，v2，v3，v4}或{v5}导出的子图都是强分图