《應(yīng)用數(shù)學基礎(chǔ)》教案4.3 樹及其應(yīng)用

長沙民政職業(yè)技術(shù)學院教案長沙民政職業(yè)技術(shù)學院教案數(shù)學應(yīng)用基礎(chǔ)課題樹及其應(yīng)用授課課時2課型新授課教案編號4-3教學目標（知識、技能、素質(zhì)）：知識目標：掌握樹的概念及破圈法、克魯斯特爾算法的具體實施步驟，家族樹、決策樹的應(yīng)用2、技能目標：分析解決問題的能力和嚴謹?shù)倪壿嬎季S能力3、素質(zhì)目標：培養(yǎng)學生理性的思維方式和數(shù)學應(yīng)用意識教學重點：樹、根樹的概念以及破圈法、克魯斯特爾算法教學難點：決策樹的應(yīng)用主要教學方法：啟發(fā)引導式、講授法教學環(huán)節(jié)與內(nèi)容一、問題引入樹是圖中一個非常重要的概念，以樹為模型的應(yīng)用領(lǐng)域非常廣泛，比如計算機、化學、地理學、植物學和心理學等。引例1(道路掃雪問題)圖4-22(a)表示的是某地區(qū)的6個鄉(xiāng)鎮(zhèn)之間的公路交通網(wǎng)絡(luò)。在冬天為了保持道路通暢，公路部門需要經(jīng)常掃雪。為了提高效率，公路部門希望只掃盡可能少的道路上的雪，但是又能確保任何兩個鄉(xiāng)鎮(zhèn)之間都存在一條干凈的道路，請問公路部門該如何設(shè)計掃雪路線？圖4-22解要設(shè)計一條掃雪路線，只需要在圖4-22(a)的基礎(chǔ)之上刪掉一些邊，來構(gòu)建一個包含所有頂點并且邊數(shù)最少的連通子圖。不難發(fā)現(xiàn)，公路部門至少需要掃除其中5條道路上的雪，才能保證任何兩個鄉(xiāng)鎮(zhèn)之間有一條干凈的道路，其中的一個清掃方案如圖4-22(b)所示。需要注意的是，圖4-22(b)只是給出了一個道路條數(shù)最少的方案，如果需要求清掃總里程最短的方案，則需要進一步知道每一條道路的里程信息。二、新課講授定義1連通而不含回路的無向圖稱為無向樹，簡稱樹。如果一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。案例1在圖4-23中哪些圖是樹？圖4-23解圖（a）是一顆無向樹，因為是無向連通圖且沒有回路。圖（b）是一棵有向樹，因為在不考慮邊的方向時是一棵樹，故是一棵有向樹。圖（c）不是樹，因為存在回路，比如回路ebade。圖（d）不是樹，因為不是連通圖。定義2若圖G的生成子圖是一棵樹，則稱這棵樹為圖G的生成樹。案例2找出圖4-24的一棵生成樹。圖4-24解因為樹中不能含有回路的，所以要找到圖的一棵生成樹，就必須把圖中的所有回路消除掉，可以通過刪除一條回路中的邊來消除這條回路并且保持圖是連通的。在圖4-24中，首先，邊ae是回路aefb的一條邊，可以刪除這條邊來消除回路aefb，如圖4-25（a）所示。其次，刪除邊ef，消除回路efge，如圖4-25（b）。最后，刪除邊cg，消除回路cgfc,如圖4-25（c）。至此，圖中不再包含回路，這樣就得到了圖4-24的一棵生成樹。圖4-25在消除回路的過程中，只要確保圖是連通的，可以刪除掉回路中的任意一條邊，故一個圖的生成樹不唯一。例如，圖4-26所示的每一棵樹都是圖4-24的生成樹。圖4-26一種尋找圖的生成樹的一般方法破圈法：（1）在圖中找到一條回路，并把該回路中的某一條邊刪掉，使它不再構(gòu)成回路。（2）重復(fù)步驟（1），直到恰好把圖中所有回路都消除掉。在實際應(yīng)用中，有大量的問題需要求連通帶權(quán)圖的一棵生成樹，使這棵生成樹的各條邊上的權(quán)值之和最小。定義3對圖的每一條邊賦予一個實數(shù)，記為，稱為邊的權(quán)，而每邊均賦予權(quán)的圖稱為帶權(quán)圖。定義4帶權(quán)圖的總權(quán)值最小的生成樹稱為最小生成樹?？唆斔固貭査惴ǖ木唧w實施步驟：（1）去掉圖中的所有邊，將圖置于只有n個頂點的初始狀態(tài)，并將圖中的邊按其權(quán)值由小到大進行排序。（2）選取權(quán)值最小的邊，若將該邊加入到圖中，不與已選取的邊構(gòu)成回路，則將此邊加入到圖中，否則舍去此邊而選取下一條權(quán)值最小的邊，依次類推，直到構(gòu)成一棵樹。案例3一個公司計劃通過租用電話線來建立一個通信網(wǎng)絡(luò)，以便連接A、B、C、D、E五個計算機中心。但是每兩個計算機中心之間的電話線租用費用不相同，如圖4-29所示。那么該公司應(yīng)當建立哪些連接，以便保證每個計算機中心都在這個通信網(wǎng)絡(luò)中，并且使得構(gòu)建網(wǎng)絡(luò)的總成本最??？圖4-27電話線租賃費用圖解要使得構(gòu)建網(wǎng)絡(luò)的總成本最小，實際上就是要找到一棵最小生成樹。利用克魯斯特爾算法尋找最小生成樹。第一步：去掉圖中的所有邊，如圖4-28(a)。第二步：選擇權(quán)值最小的邊CE添加到圖中，如圖4-28(b)。第三步：然后在剩下的邊中，依次選取權(quán)值為800的邊DE和權(quán)值為900的邊AB添加進圖中，如圖4-28(c)。第四步：接下來，再選取權(quán)值最小的邊CD，但是如果選擇CD的話，在圖中就會形成回路，故舍棄邊CD。在剩下的邊中選擇權(quán)值最小的邊AC。圖4-28克魯斯特爾算法構(gòu)造生成樹此時，所有頂點都已經(jīng)連接在圖中了，圖4-29(d)就是我們要找的最小生成樹。對應(yīng)地，連接5個計算機中心的網(wǎng)絡(luò)總成本為700+800+900+1200=3600(元)。定義5根樹是指定一個頂點作為樹根并且每條邊的方向都離開根的樹。通常一顆根樹可以看成一顆家族樹。（1）若從頂點a出發(fā)有一條邊到達頂點b，則稱b為a的兒子，a為b的父親；（2）若b，c同為a的兒子，則稱b，c為兄弟。根樹中，沒有子女的頂點稱為樹葉，有子女的頂點稱為內(nèi)點，內(nèi)點和樹根統(tǒng)稱為分支點。案例4(計算機文件系統(tǒng)圖)計算機存儲器中的文件可以組織成目錄，目錄可以包含文件和子目錄，根目錄包含整個文件系統(tǒng)。因此，文件系統(tǒng)可以表示成根樹，其中樹根表示根目錄，內(nèi)點表示文件或空目錄。在圖4-29（1）中表示了一個這樣的文件系統(tǒng)，在該系統(tǒng)中，文件khr屬于目錄rje。圖4-30一個計算機文件系統(tǒng)圖在根樹中，有向邊的方向均一致向下，故可省略掉其方向，如圖4-29中可用圖（2）代替圖（1）。決策樹：在根樹中，每個內(nèi)點都對應(yīng)著一次決策，這些頂點的子樹都對應(yīng)著該決策的每種可能后果。案例5假定有重量相同的7枚硬幣和重量較輕的一枚偽幣。為了用一架天平確定這8枚硬幣中哪個是偽幣，需要稱重多少次。解在天平上每次稱重結(jié)果只有三種可能性。分別是：兩個托盤有相同的重量、第一個托盤較重或第二個托盤較重。所以，稱重序列的決策樹是一顆3元樹。在決策樹里至少有8片樹葉，這是因為有8種可能的后果（因為每枚硬幣都可能是較輕的偽幣），而每種可能的后果必須至少用一片樹葉來表示。接下來，我們建立如圖4-30所示的決策樹。圖4-30找出偽幣位置的決策樹從圖4-30中，我們可以很容易發(fā)現(xiàn)，用兩次稱重就可以確定哪枚硬幣是偽幣。案例6有三個數(shù)a、b、c，如何建立決策樹來給這三個數(shù)按從大到小排序。解兩個數(shù)a、b比較大小只有兩種可能的情況：a大或者b大；這也就是說每次決策都會出