§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