连通和DFS ■顶点u和v连通：存在-v路 ■连通关系是定义在顶点集上的等价关系。 ■图G=<V',E>连通：中每对顶点都连通 e3 e6 eA e2 V4 es v3 2023/2/27 16
n 顶点u和v连通：存在u-v路 n 连通关系是定义在顶点集上的等价关系。 n 图G = <V, E>连通：V中每对顶点都连通 2023/2/27 16 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■连通分支：极大连通子图 ■ 平凡连通分支：阶为1 e e e6 eA ei e2 V2 V7 V8 2023/2/27
n 连通分支：极大连通子图 n 平凡连通分支：阶为1 2023/2/27 17 连通和DFS v6 v8 v7 e8 e7 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■连通分支：极大连通子图 ■平凡连通分支：阶为1 顶点集V上的连通关系将划分为若干子集 每个子集'三的点导出子图G形成一个连通分支 e e3 e6 V2 ea e1 e) V4 V] es V3 s 2023/2/27 18
n 连通分支：极大连通子图 n 平凡连通分支：阶为1 n 顶点集V上的连通关系将V划分为若干子集， 每个子集Vi ⊆ V的点导出子图G[Vi ]形成一个连通分支 2023/2/27 18 连通和DFS v6 v8 v7 e8 e7 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■若图G连通，则G连通吗？若G不连通， 则G连通吗？ Vs es e3 e6 eA e1 e2 V2 6 V7 V3 2023/2/27 19
n 若图G连通，则 连通吗？若G不连通，则 连通吗？ 2023/2/27 19 连通和DFS v6 v8 v7 e8 e7 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■若图G连通，！ 则G连通吗？若G不连通，则G连通吗？ ■自补图是连通图吗？ 1 Vs es e3 e6 e) V2 ea V6 e1 V4 V1 es V3 2023/2/27 20
n 若图G连通，则 连通吗？若G不连通，则 连通吗？ n 自补图是连通图吗？ 2023/2/27 20 连通和DFS v6 v8 v7 e8 e7 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6