第9章树 (1)1,1,2,2,2,2,2 (2)1,1,1,2,2,2,3 (3)1,1 ,2.2,4 (4)1,1 l11 1,2,3,3 (5)1,1 ,1,2,5 (6)1,1,1,1,1,3,4
第9章 树 （1）1，1，2，2，2，2，2 （2）1，1，1，2，2，2，3 （3）1，1，1，1，2.2，4 （4）1，1，1，1，2，3，3 （5）1，1，1，1，1，2，5 （6）1，1，1，1，1，3，4 （7）1，1，1，1，1，1，6
第9章树 生成树 有一些图,本身不是树,但它的某些子图却是树, 其中很重要的一类是生成树。 定义9.12若无向图G的一个生成子图T是树,则称T 是G的一棵生成树。 例如图91.3中,T1和72是图G的两棵生成树 由图913可见,G与T1、T2的区别是G中有回路,而 它的生成树无回路,因此要在一个连通图G中找到一棵 生成树,只要不断地从G的回路上删去一条边,最后所 得无回路的子图就是G的一棵生成树。于是有以下定理
第9章 树 生成树 有一些图，本身不是树，但它的某些子图却是树， 其中很重要的一类是生成树。 定义9.1.2 若无向图G的一个生成子图T是树，则称T 是G的一棵生成树。 例如图9.1.3中，T1和T2是图G的两棵生成树。 由图9.1.3可见，G与T1、T2的区别是G中有回路，而 它的生成树无回路，因此要在一个连通图G中找到一棵 生成树，只要不断地从G的回路上删去一条边，最后所 得无回路的子图就是G的一棵生成树。于是有以下定理
第9章树 76 ○ 图912
第9章 树 图 9.1.2 T1 T2 T7 T8 T9 T1 0 T1 1 T3 T4 T5 T6
第9章树 -ou2 ds3众 U 10 图913
第9章 树 图 9.1.3 e2 e3 e 4 e 1 e5 e6 e7 e8 e9 e 1 0 e2 e3 e 1 e6 e7 e 8 e2 e 4 e 1 e6 e7 e9 T2 T G 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
第9章树 定理91.3无向图G有生成树的充分必要条件是G为 连通图。 证明先采用反证法来证明必要性 若G不连通,则它的任何生成子图也不连通,因此 不可能有生成树,与G有生成树矛盾,故G是连通图 再证充分性 设G连通,则G必有连通的生成子图,令T是G的含 有边数最少的生成子图,于是T中必无回路(否则删去 回路上的一条边不影响连通性,与T含边数最少矛盾), 故T是一棵树,即生成树
第9章 树 定理9.1.3 无向图G有生成树的充分必要条件是G为 连通图。 证明 先采用反证法来证明必要性。 若G不连通，则它的任何生成子图也不连通，因此 不可能有生成树，与G有生成树矛盾，故G是连通图。 再证充分性。 设G连通，则G必有连通的生成子图，令T是G的含 有边数最少的生成子图，于是T中必无回路（否则删去 回路上的一条边不影响连通性，与T含边数最少矛盾）， 故T是一棵树，即生成树