《樹與有序樹》ppt課件

《《樹與有序樹》ppt課件》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第十章樹與有序樹10.1樹的基本概念10.2連通圖的生成樹和帶權連通圖的最小生成樹10.3有序樹10.4前綴碼和最優(yōu)二分樹例PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory樹的定義一個無向圖若連通且不含圈，則稱它為一棵樹，記為T=(V,E)。設T是一棵樹，T中度數(shù)為1的頂點稱為樹葉，度數(shù)大于1的頂點稱為分枝點。例是否為樹?例1畫出所有5個頂點的樹定理1設T=(V,E)是一棵樹，則有

2、E

3、=

4、V

5、-1。分析：對頂點數(shù)

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。根據(jù)歸納假設，有

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的元素個數(shù)歸納法來證。當

45、V

46、=1時，T是一個僅有一個頂點且沒有邊的圖。顯然，

47、E

48、

49、=0，命題成立。歸納假設若

50、V

51、≤k時，命題成立?？疾?/p>

52、V

53、=k+1時的情況。設{u’,v’}?E，我們擦去邊e,得T的一個子圖。令V1={v?V│子圖中存在u’到v的通路}，V2={v?V│子圖中存在v’到v的通路}。例定理1的證明(續(xù))新圖分為兩個連通的子圖.因為對于任意的v?V，原圖是連通的，所以在原圖中存在v到u’的通路，也存在v到v’的通路，且都是初等通路。若這兩條通路都經(jīng)過邊e，則原圖中一定有圈，故V=V1∪V2。如果存在v?V1∩V2，則原圖中存在v到u’、v到v’的兩條不經(jīng)過邊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仍連通。我們繼續(xù)這樣的工作，直到T中無圈。由于頂點與邊都是有限集，上面的工作一定可以在有限步內(nèi)終止。設T中共拿走L條邊，由于每次拿去的邊都是圈中的邊，不影響T的連通性，所以剩下的子圖T’是連通且無圈的圖，即T’是一棵樹。由定理1知，

103、V’

104、－1=

105、E’

106、，其中V’

107、，E’分別是T’的頂點和邊集。由T’的產(chǎn)生方法，有

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是連通圖?！?/p>

148、

149、Vi

150、=

151、V

152、，∑

153、Ei

154、=

155、E

156、i=1ni=1n例設G為n階無向簡單連通圖，n≥5，證明G或G的補圖不是樹。證明：若G或G的補圖都是樹，則它們的邊數(shù)都是n-1。于是(n-1)+(n-1)=n(n-1)/