第10节 图的连通性.ppt

实 例 由某条路径扩大出的极大路径不惟一，极大 路径不一定是图中最长的路径. 上图中，(1)中实线边所示的长为2的初始路径 ?，(2),(3),(4)中实线边所示的都是它扩展成的极大 路径. 还能找到另外的极大路径吗？ 扩大路径法的应用 例2: 设 G 为 n（n?3）阶无向(简单)图，? ? 2，证 明G 中存在长度 ? ?+1 的圈. 例如： {v1,v4}，{v6}是点割集. {v2,v5}是点割集吗？ {v5,v6}是点割集吗？(点割集不是割点做成的集合) {e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集. {e7,e9,e5,e6} 是边割集吗？ {e7,e8} 是边割集吗？ (边割集不是桥做成的集合) * 集合论 与图论 第10节 图的连通性 主要内容： 路、圈的定义(6.3节) 连通图(6.3节) 连通度 — 割点、桥(7.3节) —点(边)割集(7.3节) —点(边)连通度(8.1节) 通道与闭通道 定义1 设G=(V, E)是一个无向图， G的一条通道是G的顶点和边的一个交错序列 v0, x1, v1, x2, v2, x3, ..., vn-1, xn, vn, 其中xi={vi-1, vi} ，i=1, 2, ..., n. n称为通道的长. 这样的通道常称为v0-vn通道，并简记为v0v1v2...vn. v0和vn分别为通路的起点和终点. 当v0=vn时，则称此通道为闭通道. 路与圈 定义2 如果图中一条通道上的各边互不相同，则 称此通道为图的迹； 如果一条闭通道上的各边互不相同，则此闭通道 称为闭迹. 定义3 如果图中一条通道上的各顶点互不相同， 则称此通道为路或路径； 如果闭通道上各顶点互不相同，则称此闭通道为 圈，或回路. 说明：在无向图中，长度为1的圈由环构成； 长度为2的圈由两条平行边构成. 在无向简单图中，所有圈的长度?3. 例1：分析通道与闭通道，迹与闭迹，路与圈之间的关 系. v1v2v5v2v3是一条长为4的v1-v3的通道. v1v2v5v4v2v3是一条长为5的迹. v1v2v5v3是一条长为3的路. v2v4v5v2是圈. v2v4v5v2v3v2是闭通道，但不是闭迹. 例 题 通道与回路的性质 定理1 在n 阶图G中，若从顶点vi 到vj（vi?vj） 存在通道，则从vi 到 vj 存在长度小于或等于n?1 的通 道. 推论1 在 n 阶图G中，若从顶点vi 到 vj（vi?vj）存 在通道，则从vi 到vj 存在长度小于或等于n?1的路. 定理2 在一个n 阶图G中，若存在 vi 到自身的 闭通道，则一定存在vi 到自身长度小于或等于 n 的闭 通道. 推论2 在一个n 阶图G中，若存在 vi 到自身的闭 迹，则一定存在长度小于或等于n 的回路. 扩大路径法 任给一条路径，若此路径的始点或终点与路径外 的某个顶点相邻，就将它扩到路径中来，继续这一 过程，直到最后得到的路径的两个端点不与路径外 的顶点相邻为止。 最后总能得到一条极大路径. 称如此构造一条极大路径的方法为“扩大路径法”。 这是一种涉及路径和圈的构造证明中常用的方法. 设G=(V, E)为 n 阶无向图， ? 为G中一条路径。 若? 的始点和终点都不与路径?外的顶点相邻，则称 ? 是一条极大路径. 定理3 设G=(V, E)是至少有一个顶点不是弧立顶点的图，如果?u?V，degu为偶数，则G中有圈. 证 令P是G中的一条最长的路(或极大路径)， P=v1v2...vn, degv1≥2，除v2外，必有某个顶点u和v1相邻， 那么u必在P中. 所以u必是v2,...,vn中的某个vi，i≥3，于是 P=v1v2...viv1是G的一个圈. 如果u不在P中，P1=uv1v2...vn是一条更长的路; 通道与回路的性质 证：设 ? = v0v1…vl 是由初始路径 ?0 用扩大路径法 的得到的极大路径，则 l ? ? （为什么？）. 因为v0 不与 ? 外顶点相邻，又 d(v0) ? ?，因而 在 ?上除 v1外，至少还存在 ??1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶点，