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

  • 关注下方微信公众号，在线模考后查看

热门试题