什么是图的生成树？生成树主要有哪两种求法？简述二者的求解思路。
正确答案:
（1）设G是一个连通图，T是G的一个子图且是一棵树，若T包含G的所有节点，则称T是G的一棵生成树，也称支撑树。由定义可知，只有连通图才有生成树；反之，有生成树的图必为连通图。
（2）求取生成树的两种常用的方法：
破圈法：拆除图中的所有回路并使其保持连通，就能得到G的～棵生成树。
避圈法：在有n个点的连通图G中任选一条边（及其节点）；选取第2，3，„条边，使之不与已选的边形成回路；直到选取完n-1条边且不出现回路结束。
（2）求取生成树的两种常用的方法：
破圈法：拆除图中的所有回路并使其保持连通，就能得到G的～棵生成树。
避圈法：在有n个点的连通图G中任选一条边（及其节点）；选取第2，3，„条边，使之不与已选的边形成回路；直到选取完n-1条边且不出现回路结束。
答案解析:有
微信扫一扫手机做题