樹與圖的最小樹課件

樹與圖的最小樹樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。例6.2乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運動員樹與圖的最小樹例6.3某企業(yè)的組織機構(gòu)圖也可用樹圖表示。樹與圖的最小樹

樹：無圈的連通圖即為樹性質(zhì)1：任何樹中必存在次為1的點。性質(zhì)2：n個頂點的樹必有n-1條邊。性質(zhì)3：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。v1v2v3v4v5v6樹與圖的最小樹

圖的最小部分樹(支撐樹)如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2樹與圖的最小樹abcfedhgbfed樹與圖的最小樹abcfedhgbfdg樹與圖的最小樹bcedabcfedhg樹與圖的最小樹abchabcfedhg樹與圖的最小樹afdgabcfedhg樹與圖的最小樹求樹的方法：破圈法和避圈法破圈法樹與圖的最小樹部分樹樹與圖的最小樹避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5樹與圖的最小樹賦權(quán)圖中求最小樹的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)＝n-1=5樹與圖的最小樹v1v2v3v4v5v643521得到最小樹：MinC(T)=15樹與圖的最小樹避圈法:

去掉G中所有邊，得到n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通(即:n-1條邊)。5v1v2v3v4v5v6843752618樹與圖的最小樹v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123樹與圖的最小樹v1v7v4v3v2v5v61591625328174123樹與圖的最小樹v1v7v4v3v2v5v61591625328174123樹與圖的最小樹v1v7v4v3v2v5v691625328174123樹與圖的最小樹v1v7v4v3v2v5v691625328174123樹與圖的最小樹v1v7v4v3v2v5v6925328174123樹與圖的最小樹v1v7v4v3v2v5v6925328174123樹與圖的最小樹v1v7v4v3v2v5v69328174123樹與圖的最小樹v1v7v4v3v2v5v69328174123樹與圖的最小樹v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=57樹與圖的最小樹練習(xí)：應(yīng)用避圈法求最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57樹與圖的最小樹課堂練習(xí)：3749346321MinC(T)=12