计算机问题求解一论题3-7 树 2016年10月12日
计算机问题求解 – 论题3-7 - 树 2016年10月12日
Theorem 4.1 An edge e of a graph G is a bridge if and only if e lies on no cycle of G 推论：Every edge in a tree is a bridge 问题1： 从应用的角度看，上述推论有何 指导意义？
Theorem 4.1 An edge e of a graph G is a bridge if and only if e lies on no cycle of G. 推论：Every edge in a tree is a bridge
For an n-vertex graph G(with n1),the following are equiv- alent(and characterize the trees with n vertices). A)G is connected and has no cycles. B)G is connected and has n-1 edges. C)G hasn-1 edges and no cycles. D)For u,vEV(G),G has exactly one u,v-path 问题2： 如何证明一系列命题等价？ 问题3： 不能有回路对最小顶点次 数有什么影响？
树的性质的“极限性” a)Every edge of a tree is a cut-edge. b)Adding one edge to a tree forms exactly one cycle. c)Every connected graph contains a spanning tree. 问题4： 什么样的图生成树是唯一的， 为什么？
树的性质的“极限性
Theorem 4.4 Every tree of order n has size n-1. 问题：有n-1条边的n点连通图，一定是树？ 有n-1条边的无环连通图，一定连通n个点？ 问题5：如何构造一个连通图的生成树？ 无向连通图遍历算法一定得到一棵树
Theorem 4.4 Every tree of order n has size n - 1. 问题：有n-1条边的n点连通图，一定是树？ 有n-1条边的无环连通图，一定连通n个点？ 问题5：如何构造一个连通图的生成树？ 无向连通图遍历算法一定得到一棵树