离散数学第2版教学课件-有向图的连通性.pdfVIP

第十一章 图的连通性 11. 3 有向图的连通性 定义11.5 例图： 上图给出了含3个结点的强连通图、单侧连通图、弱连通图。 定义11.6 在简单有向图G中，具有强连通性质的极大子图G′称为G的强分图（或强连通分量）；具 有单侧连通性质的极大子图G”称为G的单侧分图（或单侧连通分量）；具有弱连通性质 的极大子图G’’’称为G的弱分图（或弱连通分量）。 定理11.4 一个有向图是强连通的，当且仅当G中存在经过每个顶点至少一次的回路。 证： 先证充分性，再证必要性。 （1）充分性：如果图中有一条回路，它至少包含每个结点一次，则G中任意两个结点都 是互相可达的，故G是强连通的。 （2）必要性：若有向图G是强连通的，则任意两个结点都是可达的,故必可作一回路经过 图中的所有各点。若不然则必有一回路不包含某一结点v ，而且，v与回路上的各结点不 是互相可达，与强连通的条件矛盾。 证毕。 定理11.5 在有向图G = V, E中，它的每一个结点位于且仅位于一个强分图内。 证：（1）设v V ，令S是G中所有与v相互可达的结点的集合，当然S也包括v ，而S 与顶点在S 中的边集构成的G’是G中的一个强分图，因此G中的每一个结点必位于一 个强分图中。 （2）设v位于两个不同的强分图G1和G2 中，因为G1 中的每一个结点与v可达，而v 与G2 中的每一个结点也相互可达，G1 中的每一个结点与G2 中的每一个结点通过v都 相互可达，这与题设G1为强分图矛盾，故G的每一个结点只能位于一个强分图中。 推论11.2 有向图G是单侧连通图当且仅当G中存在经过每个顶点至少一次的通路。 推论11.3 简单有向图中的每个结点和每条边恰好位于一个弱分图中。 小结 理解有向图的连通性、单侧连通、强连通和弱连通及它们的性质。关于有向图的连 通性的思维形式注记图如下图所示。 至少有一个结点 到另一个结点 单侧连通 可 有 向 图 达 任意结点 强连通 充要条件 略去方向 无向图 连通 弱连通 小结 图 k(G) ≤λ(G) 回路 始点 终点 路径 存在路 无 割点 点割集 向 连 点连通度、边连通度 通