北大離散數(shù)學chap-在線瀏覽
2024-09-15 04:01本頁面
【正文】 度數(shù)序列： (4) 1 1 1 2 2 34T5T例 畫出所有的 6個頂點的非同構的樹。 例 (2) 一棵樹有 2個 4度頂點， 3個 3度頂點， 其余都是樹葉，求這棵樹共有多少個頂點？ 解： 設有 片樹葉，則頂點數(shù) x 23 x?? ， 邊數(shù) 2 3 1x? ? ? ， 由握手定理， 2 4 3 3 2 (2 3 1 )xx? ? ? ? ? ? ? ?， 解得 9x? ， 故頂點總數(shù)為 2 3 9 1 4? ? ? 個。 定義： 設 是無向連通圖， ,G V E? T是 G的生成子圖，若 T 是樹，稱 T 是 G 的生成樹。 例 (3 )( 2)( 1 )上圖中， (2)是 (1)的生成樹， (3)是 (2)的余樹。 連通圖的性質 。T 是 T 的余樹， 則 39。 已知連通圖 ，求其生成樹步驟。 對于有向圖或無向圖 的每條邊附加一個實數(shù) G()we ，則稱 ()we 為邊 e 上的 權 ， G 連同附加在 各邊上的實數(shù)稱為 帶權圖 ，記為 ,G V E W?。 定義： 設無向連通帶權圖 ,G V E W?， T 是 G 的一棵生成樹， T 各邊帶權之和稱為 T 的權， 記作 ()WT。 設 階無向連通帶權圖 n,G V E W?中有 m 條 邊 12, , , me e e，它們帶的權分別為 12, , , ma a a， 不妨設 12 ma a a? ? ?， (1) 取 1e在 T 中 (非環(huán)，若 1e為環(huán)，則棄 1e)。 c defba解： 1T例 求以下連通圖的最小生成樹 及 T()WT。T例 求以下連通圖的最小生成樹 及 T()WT。) 1 5 ( )W T W T??fedcba解： 2T例 求以下連通圖的最小生成樹 及 T()WT。T例 求以下連通圖的最小生成樹 及 T()WT。) 1 8 ( )W T W T??注意： 的最小生成樹可能不唯一， G但 G 的不同最小生成樹權的值一樣。 重點： 有向樹及根樹的定義， 家族樹，有序樹， 元樹的概念， r最優(yōu) 2元樹的概念及哈夫曼 ()H u ffm a n算法。 有向樹 ： 一個有向圖 ，若略去有向邊的 D方向所得的無向圖為一棵無向樹，則稱 D 為 有向樹 。 根樹的頂點 樹葉 (入度為 1，出度為 0) 分支點 樹根 (入度為 0) 內點 (入度為 1， 出度大于 0) 例 例 樹高。 樹高 —— 樹中頂點的最大層數(shù)，記 ()hT 。 一棵根樹可以看成一棵 家族樹 。 根子樹。 T8v7v6v5v4v3v2v1v例 3v39。 r 有序樹 —— 每一層上都規(guī)定次序的根樹。 rr 元正則樹 —— 每個分支點恰有 個兒子的根樹。 rr 元有序完全正則樹 注意： 2元有序正則樹是最重要的一種 r 元樹。 r 元完全正則樹 的層數(shù)相同 (等于樹高 )。 (1) 的 權 T最優(yōu) 2元樹 —— 權最小的 2元樹。 記為 1( ) ( )tiiiW T w L w?? ?例 下圖中的 都是帶權 1
法律信息相關推薦
鄂ICP備17016276號-1