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

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