北大離散數(shù)學chap-免費閱讀
【正文】 T m t證明： ，其中 22mt?? 2t? 。 kn個頂點的度數(shù)為 k ，而其余的 頂點都是樹葉。 (1) 2個頂點 (2) 3個頂點 (3) 4個頂點 例 畫出滿足下列要求的所有非同構的無向樹。 二、根樹及其應用。 (1) 無向樹的六個等價定義。為了使整個信息的長度盡可能短，自然希望用較短的符號串去表示使用頻率高的英文字母，用較長的符號串表示使用頻率低的英文字母。 例 求帶權 1, 3, 4, 5, 6的最優(yōu) 2元樹 及 T ()WT 。 (1) 的 權 T最優(yōu) 2元樹 —— 權最小的 2元樹。 r 有序樹 —— 每一層上都規(guī)定次序的根樹。 樹高 —— 樹中頂點的最大層數(shù)，記 ()hT 。) 1 8 ( )W T W T??注意： 的最小生成樹可能不唯一， G但 G 的不同最小生成樹權的值一樣。 c defba解： 1T例 求以下連通圖的最小生成樹 及 T()WT。 已知連通圖 ，求其生成樹步驟。 定義： 設 是無向連通圖， ,G V E? T是 G的生成子圖，若 T 是樹，稱 T 是 G 的生成樹。 T例 畫出所有的 6個頂點的非同構的樹。 定理： 設 ,G V E? Vn? Em?， ， ， 則以下命題等價。 無向樹簡稱樹，常用 表示。 本章中所談回路均指簡單回路或初級回路。 G(2) 的每對頂點間具有唯一的路徑。 (1) 樹中頂點數(shù)與邊數(shù)的關系： 1nm?? 。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產生以下五種 度數(shù)序列： (5) 1 1 2 2 2 26T例 (1) 一棵樹有 7片葉， 3個 3度頂點，其余都 是 4度頂點，求 4度頂點多少個？ 解： 設有 個 4度頂點，則頂點數(shù) x 73 x?? ， 邊數(shù) 7 3 1x? ? ? ， 由握手定理， 4 3 3 7 2 ( 7 3 1 )xx? ? ? ? ? ? ?， 解得 1x? ， 故這棵樹有 1個 4度頂點。 設 ,G V E?為連通圖， Vn?， Em?， (1) 至少有一棵生成樹， G(2) 1mn?? ， (3) 設 是 T G 的生成樹， 39。 求最小生成樹的方法 K ru skal—— 避圈法 。 ( 2 )9877643 21105abcdef123572( ) 1 8WT ?753 21fedcba解： 239。 根樹 ： 一棵非平凡的有向樹，如果有一個 頂點的入度為 0，其余頂點的入度均為 1，則 稱此有向樹為 根樹 。 樹 的 根子樹 T —— T 的非樹根的頂點 a 及其 后代導出的子圖。 有序樹 —— 每一層上都規(guī)定次序的根樹。 解： 3( ) ( 1 3 ) 3 (6 4 5 ) 2 4 2WT ? ? ? ? ? ? ? ?3T6 54313 1 2( ) ( ) ( )W T W T W T??但不能判定 3T是最優(yōu) 2元樹。 1 4 0求最佳前綴碼。 基本概念。 運用。 (1) 按定義畫出 等等。 解： 2G的生成樹有： 2G例 一棵樹有 個頂點的度數(shù)為 2， 2n 3
法律信息相關推薦
鄂ICP備17016276號-1