《树与有序树》ppt课件

《《树与有序树》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章树与有序树10.1树的基本概念10.2连通图的生成树和带权连通图的最小生成树10.3有序树10.4前缀码和最优二分树例PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory树的定义一个无向图若连通且不含圈，则称它为一棵树，记为T=(V,E)。设T是一棵树，T中度数为1的顶点称为树叶，度数大于1的顶点称为分枝点。例是否为树?例1画出所有5个顶点的树定理1设T=(V,E)是一棵树，则有

2、E

3、=

4、V

5、-1。分析：对顶点数

6、V

7、进行归纳法证明。当

8、V

9、=1和

10、V

11、=2时，定

12、理显然是成立的。归纳假设当

13、V

14、≤k时，定理成立。考察

15、V

16、=k+1时的情况。因为树无圈，所以从T中去掉任何一条边，都会使T变成具有两个连通分支的不连通图。这两个连通分支也必然是树，譬如说是T1=(V1,E1)和T2=(V2,E2)。显然，

17、V1

18、≤k,

19、V2

20、≤k。根据归纳假设，有

21、E1

22、=

23、V1

24、-1,

25、E2

26、=

27、V2

28、-1。而

29、V

30、=

31、V1

32、+

33、V2

34、,

35、E

36、=

37、E1

38、+

39、E2

40、+1,所以

41、E

42、=

43、V

44、-1,即定理得证。定理1的证明证明：用对顶点集V的元素个数归纳法来证。当

45、V

46、=1时，T是一个仅有一个顶点且没有边的图。显然，

47、E

48、

49、=0，命题成立。归纳假设若

50、V

51、≤k时，命题成立。考察

52、V

53、=k+1时的情况。设{u’,v’}∊E，我们擦去边e,得T的一个子图。令V1={v∊V│子图中存在u’到v的通路}，V2={v∊V│子图中存在v’到v的通路}。例定理1的证明(续)新图分为两个连通的子图.因为对于任意的v∊V，原图是连通的，所以在原图中存在v到u’的通路，也存在v到v’的通路，且都是初等通路。若这两条通路都经过边e，则原图中一定有圈，故V=V1∪V2。如果存在v∊V1∩V2，则原图中存在v到u’、v到v’的两条不经过边e的初等通路，加上边e后,原图中一定有圈，

54、故V1∩V2=Ø。新图分为两棵不相交的树.原图无圈，子图也不会有圈，即为两棵不相交的树(顶点的交集为空集)。设T1=(V1,E1)，T2=(V2,E2)，由归纳假定有

55、V1

56、-1=

57、E1

58、，

59、V2

60、-1=

61、E2

62、。又

63、V

64、=

65、V1

66、+

67、V2

68、，

69、E

70、=

71、E1

72、+

73、E2

74、+1。所以有定理得证。定理1的推论任何一棵至少含有两个顶点的树至少有两片树叶。证明：设T=(V,E)是一棵树，若T中最多只有一片树叶，则有∑d(v)≥1+2(

75、V

76、-1)=2

77、E

78、+1,这与结论∑d(v)=2

79、E

80、矛盾!矛盾说明T不止一片树叶。v∊Vv∊V例设T为树，最大

81、度△≥k，这里k≥1，证明T至少有k片树叶。证明：假设T有s片树叶，s

82、E

83、=2(

84、V

85、-1)=2(5+3+3+x－1)∴x=15定理2T=(V,E)是一个简单图，以下三条等价。①T是一棵树。②T

86、连通,且

87、V

88、－1=

89、E

90、。③T中无圈,且

91、V

92、－1=

93、E

94、。证明：由①推出②，由②推出③，再由③推出①，以完成整个定理的证明。①②T是一棵树，即T连通且无圈，由定理1知，有

95、V

96、－1=

97、E

98、。定理2的证明②③已知T连通且

99、V

100、－1=

101、E

102、。若T中有圈，拿去圈中的一条边，T仍连通。我们继续这样的工作，直到T中无圈。由于顶点与边都是有限集，上面的工作一定可以在有限步内终止。设T中共拿走L条边，由于每次拿去的边都是圈中的边，不影响T的连通性，所以剩下的子图T’是连通且无圈的图，即T’是一棵树。由定理1知，

103、V’

104、－1=

105、E’

106、，其中V’

107、，E’分别是T’的顶点和边集。由T’的产生方法，有

108、V’

109、=

110、V

111、，

112、E’

113、=

114、E

115、－L。所以

116、V

117、－1=

118、E

119、－L。由于

120、V

121、－1=

122、E

123、，所以

124、E

125、=

126、E

127、－L，即L=0，原图无圈。定理2的证明③①已知T中无圈且

128、V

129、－1=

130、E

131、。若T不连通，设T有k个连通分枝：T1，T2，…，Tk，Ti=(Vi,Ei),1≤i≤k。对于每一个i(1≤i≤k),Ti是连通的且无圈，故Ti是树。由定理1知，

132、Vi

133、－1=

134、Ei

135、，1≤i≤k。又所以

136、V

137、－k=

138、E

139、，而已知

140、V

141、－1=

142、E

143、，即有

144、V

145、－k=

146、V

147、－1，故k=1，即T是连通图。∑

148、

149、Vi

150、=

151、V

152、，∑

153、Ei

154、=

155、E

156、i=1ni=1n例设G为n阶无向简单连通图，n≥5，证明G或G的补图不是树。证明：若G或G的补图都是树，则它们的边数都是n-1。于是(n-1)+(n-1)=n(n-1)/