西安电子科技大学$6.7.2 生成树软件学院需定理」一个连通无向图至少有一棵生成树。证明：（构造法）设G是连通无向图，若G中没有简单回路，则G本身就是生成树。若G中存在简单回路，任选一条简单回路C1，从C1中删去一条边得到G1。若G1中无简单回路了，则G1是G的一棵生成树，若G1中仍有简单回路，则从G1中任选一条简单回路C2，从C2中删去一条边得到G2，重复上述过程，由于G中的简单回路数是有限的，故最终可以得到G的一棵生成树。西安电子科技大学 §6.7.2 生成树 软件学院 证明：（构造法） 设G是连通无向图，若G中没有简单回路，则G本身 就是生成树。 若G中存在简单回路，任选一条简单回路C1，从C1 中删去一条边得到G1。若G1中无简单回路了，则G1是 G的一棵生成树，若G1中仍有简单回路，则从G1中任选 一条简单回路C2，从C2中删去一条边得到G 2，. 重复上述过程，由于G中的简单回路数是有限的，故最 终可以得到G的一棵生成树