最小支撐樹(shù)樹(shù)的概念關(guān)于樹(shù)的性質(zhì)圖的生成樹(shù)最小支撐樹(shù)

最小支撐樹(shù)1、樹(shù)的概念2、關(guān)于樹(shù)的性質(zhì)3、圖的生成樹(shù)4、最小支撐樹(shù)5、最小支撐樹(shù)求解6、最小支撐樹(shù)在實(shí)際中應(yīng)用樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達(dá)成一個(gè)樹(shù)圖。例10乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動(dòng)員樹(shù)與圖的最小樹(shù)例11某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。樹(shù)葉分枝點(diǎn)連通且不含圈的無(wú)向圖稱為樹(shù)。樹(shù)中次為1的點(diǎn)稱為樹(shù)葉樹(shù)中次大于1的點(diǎn)稱為分枝點(diǎn)1、樹(shù)的概念2、關(guān)于樹(shù)的性質(zhì)（1）一棵樹(shù)的邊數(shù)等于點(diǎn)數(shù)減1；（2）在樹(shù)中任意兩個(gè)點(diǎn)之間添加一條邊就形成圈；（3）在樹(shù)中去掉任意一條邊圖就變?yōu)椴贿B通。

（4）樹(shù)中任意兩點(diǎn)之間，有惟一鏈相連。3、圖的生成樹(shù)若圖G的生成子圖是一棵樹(shù)，則稱該樹(shù)為G的生成樹(shù)（支撐樹(shù)）。簡(jiǎn)稱為圖G的樹(shù)。v6v5v2v3v4v1v6v5v3v4v1v2在一個(gè)連通圖G中，取部分邊連接G的所有點(diǎn)組成的樹(shù)稱為G的部分樹(shù)或支撐樹(shù)(SpanningTree

)。圖6－2是圖6－1的部分樹(shù)。v1v2v3v4v5v64321圖6－255v1v2v3v4v5v6843752618圖6－120四月20254、最小支撐樹(shù)圖G的所有部分樹(shù)中長(zhǎng)度最小的部分樹(shù)稱為最小支撐樹(shù)，或簡(jiǎn)稱為最小樹(shù)。尋找最小支撐樹(shù)的方法（1）破圈法：取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。（2）避圈法（加邊法）：取圖G的n個(gè)孤立點(diǎn)｛v1，v2，…，vn}作為一個(gè)支撐圖，從最短邊開(kāi)始往支撐圖中添加，見(jiàn)圈回避，直到連通（有n－1條邊）

20四月20255v1v2v3v4v5v6843752618圖6－1【例12】用破圈法求圖6－1的最小樹(shù)。圖6－4圖6－4就是圖6－1的最小部分樹(shù)，最小樹(shù)長(zhǎng)為

C(T)=4+3+5+2+1=15。當(dāng)一個(gè)圈中有多個(gè)相同的最長(zhǎng)邊時(shí)，不能同時(shí)都去掉，只能去掉其中任意一條邊。最小部分樹(shù)有可能不唯一，但最小樹(shù)的長(zhǎng)度相同20四月2025v1v2v3v4v5v643521圖6－5在圖6－5中，如果添加邊[v1,v2]就形成圈｛v1,v2,v4｝，這時(shí)就應(yīng)避開(kāi)添加邊[v1,v2]，添加下一條最短邊[v3,v6]。破圈法和加邊法得到樹(shù)的形狀可能不一樣，但最小樹(shù)的長(zhǎng)度相等5v1v3v515v2v4v684375268×MinC(T)=15【例13】用加邊法求圖6－1的最小樹(shù)圖6－1例14某物流中心有9個(gè)分銷點(diǎn)，道路如圖所示，要以V0為中心建立有限廣播網(wǎng)絡(luò)，要求沿著道路架設(shè)廣播線，問(wèn)如何拉線才能使線最短？V1V2V8V7V6V5V3V4V0253