回覆列表
-
1 # 心心31925
-
2 # 何小冷大大貓
邊權就是其頂點的權值差。
離散數學或資料結構中,圖的每條邊上帶的一個數值,他代表的含義可以是長度等等,這個值就是邊權。
在此圖中即線條兩端點構成的向量值。
可以把每個向量用ae^iθ的形式表示。以邊長為1,則邊V2V1=e^i(π/5),v2v5=2cos(π/5),v5v1=e^i(4π/5),V5V4=e^i(7π/5),V2V3=e^i(9π/5),V3V4=1,V2V4=2cos(π/5)e^i(-π/5),V4V41=2cos(π/5)e^i(3π/5)
樹的權指的樹中的結點被賦予的一個有某種意義的數,這個數我們就稱它為權.權對樹本身沒意義,但對實際應用卻很有用,比如說資訊傳送中,文章都是用碼錶示的,我們當然是要碼長越短,傳送時間越短.若字母A,B,Z,C出現的機率為0.75,0.54,0.28,0.43;如何編碼使傳送的文章碼長最短呢?這時權就有用了.設相應的權值為:75,54,28,43.構造一棵樹,求出結點的帶權路徑長度最小的就是碼長最小的了,我們以這種編碼方式去編碼,就會得到最小碼長.當然我們都知道哈夫曼樹的權路徑最短,這個就不說了.