§71图的基本概念 4连通图(强连通图) 在无(有)向图G<V,E>中,若对任何两个顶点ⅴ、u都 存在从ⅴ到u的路径,则称G是连通图(强连通图) 连通图 V3)(V4 非连通图 voV 强连通图 非强连通图
4 连通图（强连通图） 在无（有）向图G=< V, E >中，若对任何两个顶点 v、u 都 存在从v 到 u 的路径，则称G是连通图（强连通图） §7.1 图的基本概念 非 连 通 图 连 通 图 强 连 通 图 非 强 连 通 图 V0 V1 V2 V3 V0 V3 V4 V1 V2 V0 V1 V2 V3 V0 V3 V2 V1 V5 V4
§71图的基本概念 5子图 设有两个图G=(V,E)、Gl=(V1,E1),若V1cV,E1c E,E关联的顶点都在V1中,则称G1是G的子图; 例(b)、(c)是(a)的子图 0⑩ vo(V1 V2 V3) V4) a
5 子图 设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1 E，E1关联的顶点都在V1中，则称G1是G的子图； 例 (b)、(c) 是 (a) 的子图 (a) (b) (c) §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V3 V4 V1 V2 V0 V3 V4 V1 V2
6连通分图(强连通分量) §71图的基本概念 无向图G的极大连通子图称为G的连通分量 极大连通子图意思是:该子图是G连通子图,将G的任何不 在该子图中的顶点加入,子图不再连通; 非连通分图 连通分图 非连通图 vo( v4 V3 5
6 连通分图（强连通分量） 无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是：该子图是G 连通子图，将G 的任何不 在该子图中的顶点加入，子图不再连通； 连通分图 非 连 通 图 §7.1 图的基本概念 V0 V3 V2 V1 V5 V4 V0 V2 V1 非连通分图
有向图D的极大强连通子图称为D的强连通分量 极大强连通子图意思是:该子图是D强连通子图,将D的任何 不在该子图中的顶点加入,子图不再是强连通的; 强连通分量 VO V2)(9
有向图D 的极大强连通子图称为D 的强连通分量 极大强连通子图意思是：该子图是D强连通子图，将D的任何 不在该子图中的顶点加入，子图不再是强连通的； 强连通分量 V0 V1 V2 V3 V0 V2 V3 V1
§71图的基本概念 7生成树 包含无向图G所有顶点的的极小连通子图称为G的生成树 极小连通子图意思是:该子图是G的连通子图,在该子图中删除任何一条 边,子图不再连通, 若T是G的生成树当且仅当T满足如下条件 T是G的连通子图 T包含G的所有顶点 T中无回路 VO) V3 V4 V3) V4 连通图G1 G1的生成树
7 生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树 极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一条 边，子图不再连通， 若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路 连通图 G1 G1的生成树 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V3 V4 V1 V2 V0 V4 V3 V1 V2