您當前所在位置:首頁 > PPT課件 > 數學課件PPT → 離散數學二叉搜索樹ppt

離散數學二叉搜索樹ppt

PPT預覽

離散數學二叉搜索樹ppt

PPT內容

這是離散數學二叉搜索樹ppt下載,主要介紹了無向樹及生成樹;根樹及其應用,歡迎點擊下載。

第10章 樹與有序樹 9.1 無向樹及生成樹 9.2 根樹及其應用 第十章 樹與有序樹 10.1 樹的基本概念 (一) 樹的定義 (二) 樹的等價定義例 無向樹無向樹: 連通無回路的無向圖平凡樹: 平凡圖森林: 每個連通分支都是樹的非連通的無向圖樹葉: 樹中度數為1的頂點分支點: 樹中度數2的頂點右圖為一棵12階樹. 聲明:本章中所討論的回路均 指簡單回路或初級回路無向樹的性質定理1 設G=是n階m條邊的無向圖,則下面各命題是等價的:(1)G是樹(連通無回路); (2)G中任意兩個頂點之間存在惟一的路徑; (3)G中無回路且m=n1; (4)G是連通的且m=n1; (5)G是連通的且G中任何邊均為橋; (6)G中沒有回路, 但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈. 無向樹的性質(續) 例1 已知一棵樹有5個4度頂點,3個3度頂點,3個2度頂點,問有幾個一度頂點?例2 已知無向樹T有5片樹葉, 2度與3度頂點各1個, 其余頂點的度數均為4. 求T的階數n, 并畫出滿足要求的所有非同構的無向樹. 解 設T的階數為n, 則邊數為n1, 4度頂點的個數為n7. 由握手定理得 2m=2(n1)=51+21+31+4(n7) 解出n=8, 4度頂點為1個. T的度數列為1,1,1,1,1,2,3,4 有3棵非同構的無向樹 10.2 連通圖的生成樹和帶權連通圖的最小生成樹 (一) 生成樹 (二) 基本圈、基本割集 (三) 生成樹與基本圈、基本割集的關系 (四) 最小生成樹 (五) 避圈法例假設有分布在不同建筑物中的5臺計算機。計算機連接的可能方案如右圖所示。生成樹定義:設G=(V,E)是一個連通圖, G的一個生成子圖若本身是一棵樹, 稱它為G的一棵生成樹。定理1 任何連通圖都有生成樹。證明:設G=(V,E)是一個簡單連通圖. 若G中無圈,則G 本身是G的一棵生成樹。 若G中有圈,拿去圈中一條邊,原圖仍連通。若再有圈,再拿去圈中一條邊,直到G中無圈為止。因為G中頂點與邊均為有限數,故上述工作一定可以在有限步內結束。 G的這個無圈的連通子圖就是G中一顆生成樹。例1 G若有生成樹,一般不唯一生成樹的枝、弦設G=(V,E)是一個圖,TG=(V,D)是G的一棵生成樹。 稱e∊D為TG的枝, 稱e∊E但e∉D為TG的弦。基本圈(回路)系統 對于生成樹TG的每一個弦,對應于G中的唯一的一個含且僅含該弦的基本圈。 G中由所有弦所分別對應的基本圈組成了G關于TG的基本圈系統。 基本割集設e={u0,v0} ∊D是TG的枝。令 V1={v∊V │v=u0或在 TG中 v與u0之間有不經過邊 e的通路}, V2={v∊V │v=v0或在 TG中 v與v0之間有不經過邊 e的通路}, 則 D’={ {u,v} ∊E│u∊V1, v∊V2}是G的一個割集。 這樣的割集叫G關于TG的基本割集。 所有的這樣的基本割集組成了基本割集系統。實例例 圖中紅邊為一棵生成樹, 求對應它的基本回路系統 與基本割集系統解 弦e,f,g對應的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, Cf, Cg}. 樹枝a,b,c,d對應的基本割集分別為 Sa={a, f, g}, Sb={b, e, f, g}, Sc={c, e, f g}, Sd={d, g}, S基={Sa, Sb, Sc, Sd}. 帶權圖的最小生成樹 例 假設有分布在不同建筑物中的5臺計算機C1, C2, C3, C4, C5。計算機連接的可能方案以及每種連接方式的成本(單位:元)如右圖所示。帶權圖的最小生成樹設G=(V,E, φ)是一個帶權連通圖, φ:E→R+,R+ ={x∊R│x>0}。 TG=(V,D)是G中一棵生成樹,可定義TG的權值如下: φ(TG) = ∑ φ(e) 帶權圖的最小生成樹避圈算法(Kruskal) 普里姆(Prim)算法避圈算法的指導思想避圈算法步驟 (1) 把G中的邊按權值大小排序。設有m條邊e1,e2,…,em,它們的權值分別為a1,a2,…,am,不妨設a1≤a2≤⋯⋯≤am。 (2) 按邊的權值大小次序,從最小邊開始,畫上權值最小的邊(即取e1)為生成樹的枝。 (3) 設e是未被考察的邊中權值最小的邊,若把e畫上作為生成樹的枝,所得子圖不產生圈,則選e為生成樹的枝,否則不把e畫上。 (4) 看選上作為生成樹的邊的條數是否等于|V|-1。若等于|V|-1 ,則終止。否則轉向(3)。例 求最小生成樹普里姆(Prim)算法兩種算法的評價 10.3 有序樹 (一) 有向樹 (二) 根樹 (三) 有序樹(第i子樹) (四) m-分樹 (五) 2-分樹/正則2-分樹有向樹定義1 一個有向圖,若去掉邊的方向,所得無向圖是一棵樹,則稱這個有向圖為有向樹。根樹設T=(V,E)是一棵有向樹,若僅有一個頂點的入度為0,其余的頂點的入度均為1,這樣一棵有向樹我們稱為根樹。入度為0的頂點稱為樹根,出度為0的頂點稱為樹葉,出度不為0的頂點稱為分枝點。 例 畫出4階所有非同構的根樹 家族樹設T=(V,E)是一棵根樹,將其看做看做家族樹如果e=(v,u) ∊E,稱v是u的父親, u是v的兒子。對v1,v2∊V,若存在一條從v1到v2的通路,則稱v1是 v2的祖先,v2是v1的后代。若(v0,v1),(v0,v2) ∊E ,說v1與v2是兄弟。子樹設T=(V,E)是一棵根樹。 v0∊V,v0是 中一個分支點, 所謂以v0為根的子樹是指T的一個子圖T ’,T ’以v0和v0的全部的后代為頂點,以從v0出發的所有通路經過的邊為邊。以v0的一個兒子為根的子樹稱為v0的子樹。根樹的分類有序樹: 將根樹同層上的頂點規定次序 r元樹:根樹的每個分支點至多有r個兒子 r元正則樹: 根樹的每個分支點恰有r個兒子 r元有序樹: 有序的r元樹 r元正則有序樹: 有序的r元正則樹最優2元樹 求最優樹 Huffman算法: 給定實數w1, w2, …, wt, ① 作t片樹葉, 分別以w1, w2, …, wt為權. ② 在所有入度為0的頂點(不一定是樹葉)中選出兩個權最小的頂點, 添加一個新分支點, 以這2個頂點為兒子, 其權等于這2個兒子的權之和. ③ 重復②, 直到只有1個入度為0 的頂點為止. W(T)等于所有分支點的權之和實例例 求帶權為1, 1, 2, 3, 4, 5的最優樹. 解題過程由下圖給出,W(T)=38 小結 樹與有序樹 無向樹及生成樹 ( m=n1) 基本回路與基本回路系統 基本割集與基本割集系統 最小生成樹 根樹及其應用 r元樹(r元有序樹) r元正則樹(r元有序正則樹) r元完全正則樹(r元有序完全正則樹) 最優2元樹與Huffman算法

相關PPT

20120515即刻搜索合作簽約儀式0515ppt:這是20120515即刻搜索合作簽約儀式0515ppt,包括了會議策劃背景,會議空間設計,會議流程設計,會議創意亮點,會議策劃實施,活動費用預算,聯合服務團隊等內容,歡迎點擊下載。
小學科學校園生物大搜索ppt:這是小學科學校園生物大搜索ppt下載,主要介紹了身邊的生物世界;常見動物;常見植物;其他生物,歡迎點擊下載。
人工智能導論課件(李俊麗)ch2搜索與求解ppt:這是人工智能導論課件(李俊麗)ch2搜索與求解ppt,包括了搜索概述,狀態空間搜索,狀態空間盲目搜索,狀態空間啟發式搜索,代價樹的搜索,與/或樹搜索,博弈樹的啟發式搜索等內容,歡迎點擊下載。
《離散數學二叉搜索樹ppt》是由用戶huangyixuan于2019-11-29上傳,屬于數學課件PPT。

標簽:

相關PPT

縮略圖

  • 離散數學二叉搜索樹ppt
赛车pk10计划群 微乐福建麻将下载安装 黑龙江体彩11选五开奖 股票配资渠道 即时篮球比分球探 海南七星彩票 青海11选五5开奖 法国和乌拉圭胜比分预测 山西快乐十分的玩法 北京pk10介绍 排列三中奖号 体球网即时比分手机版 打杭州麻将必胜绝技