计算机问题求解一论题3-6 树 2022年10月19日
计算机问题求解 – 论题3-6 - 树 2022年10月19日
Theorem 4.1 An edge e of a graph G is a bridge if and only if e lies on no cycle of G. tree:无环连通图 推论：Every edge in a tree is a bridge 问题1g 从应用的角度看。上述推论有何指导意义？
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 tree：无环连通图
从同构的角度看，有个点的不同构的树，有多少个？ T2 Ta T, 我们有T(n)=1,1,1,1,2,3,6,11,23,47,106,235,551,1301,3159,. Otter(1948)proved the asymptotic estimate t(n)~Ca"n5/2asn→o, with the values C and a known to be approximately 0.534949606...and 2.95576528565
从同构的角度看，有n个点的不同构的树，有多少个？ 我们有T(n) =
树、根树和有向树有什么差别？ 备注：如果我们只谈树，没有父子兄弟之概念
树、根树和有向树有什么差别？ 备注：如果我们只谈树，没有父子兄弟之概念
For an n-vertex graph G(with n>1),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 has n-1 edges and no cycles. D)For u,vV(G),G has exactly one u,v-path. 问题2： 如何证明一系列命题等价？ 问题38 不能有回路对最小顶点度数有什么影响？
Theorem 4.3 Every nontrivial tree has at least two end-vertices. Proof.Let T be a nontrivial tree and among all paths in T, let P be a path of greatest length. 口 Suppose that P is a u-v path,say P=(u=uo,u,...uk=v), where k=1.We show that u and v are end-vertices of G. Necessarily,neither u nor v is adjacent to any vertex not on P,for otherwise,a path of greater length would be produced.Certainly,u is adjacent to u on P and v is adjacent to uk-1 on P. Moreover,since T contains no cycles,neither u nor v is adjacent to any other vertices in P.Therefore,deg u=deg v=1
Theorem 4.3 Every nontrivial tree has at least two end-vertices. ◼ Proof. Let T be a nontrivial tree and among all paths in T, let P be a path of greatest length. ❑ Suppose that P is a u − v path, say P = (u = u0 , u1 , …, uk = v), where k ≥ 1. We show that u and v are end-vertices of G. ❑ Necessarily, neither u nor v is adjacent to any vertex not on P, for otherwise, a path of greater length would be produced. Certainly, u is adjacent to u1 on P and v is adjacent to uk −1 on P. ❑ Moreover, since T contains no cycles, neither u nor v is adjacent to any other vertices in P. Therefore, deg u = deg v = 1
Theorem 4.4 Every tree of order n bas size n-1. Proof.We proceed by induction on n. There is only one tree of order 1,namely K1,which has size 0.Thus the result is true for n=1. Assume for a positive integer k that the size of every tree of order k is k-1. Let Tbe a tree of order k+1.By Theorem 4.3,T contains at least two end-vertices.Let v be one of them.Then T=T-v is a tree of order k.By the induction hypothesis,the size of T'is m =k-1. Since Thas exactly one more edge than T,the size of Tis m+1 (k-1)+1=(k+1)-1,as desired
Theorem 4.4 Every tree of order n has size n − 1. ◼ Proof. We proceed by induction on n. ❑ There is only one tree of order 1, namely K1 , which has size 0. Thus the result is true for n = 1. ❑ Assume for a positive integer k that the size of every tree of order k is k − 1. ❑ Let T be a tree of order k + 1. By Theorem 4.3, T contains at least two end-vertices. Let v be one of them. Then T′ = T − v is a tree of order k. By the induction hypothesis, the size of T′ is m = k − 1. Since T has exactly one more edge than T′, the size of T is m + 1 = (k − 1) + 1 = (k + 1) − 1, as desired
关于树的另外一个性质 Theorem 4.9 Let T be a tree of order k.If G is a graph withδ（可≥k-1,then T is isomorphic to some subgraph of G
关于树的另外一个性质 Theorem 4.9 Let T be a tree of order k. If G is a graph with δ(G) ≥ k − 1, then T is isomorphic to some subgraph of G
Theorem 4.9 Let T be a tree of order k.If G is a graph with Image(G)=k-1,then T is isomorphic to some subgraph of G ■对k进行数学归纳法证明 ■奠基：K=1,2时显然成立：孤立点、一条边 ■假设：T有k-1点，H的最小度大于等于k-2,结论成立 ■归纳：T有k点，G的最小度大于等于k-1 口令V是T中端点，u是v的相邻点； 口从T中删除V,命名新树为T,T'同构与G的某个子图F。令u是F中u的同构点 DegG(u)>=k-1,而F只有k-1个点，u一定有一个 不属于V(F)的相邻点w,那么F基础上加上点W 以及uw边，构成一棵树F G 口T和F同构，F'是G的子图
Theorem 4.9 Let T be a tree of order k. If G is a graph with Image(G) ≥ k − 1, then T is isomorphic to some subgraph of G. ◼ 对k进行数学归纳法证明 ◼ 奠基：K=1,2时显然成立：孤立点、一条边 ◼ 假设：T’有k-1点，H的最小度大于等于k-2，结论成立 ◼ 归纳：T有k点，G的最小度大于等于k-1 ❑ 令v是T中端点，u是v的相邻点； ❑ 从T中删除v，命名新树为T’, T’同构与G的某个子图F。令u’是F中u的同构点 ❑ DegG(u’)>=k-1，而F只有k-1个点，u’一定有一个 不属于V(F)的相邻点w，那么F基础上加上点w 以及u’w边，构成一棵树F’ ❑ T和F’同构，F’是G的子图
树的性质的“极限性” 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： 什么样的图生成树是唯一的，为什么？
树的性质的“极限性