【正文】 5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 總造價(jià) =1+4+9+3+17+23=57 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 避圈法 ：開始選一條 權(quán)最小 的邊 ， 以后每一步中 ，總從未被選取的邊中選一條權(quán)盡可能小 ， 且與已選邊不構(gòu)成圈的邊 。 具有最小權(quán)的生成樹 ， 稱為最小生成樹 。 用破圈法求出下圖的一個(gè)生成樹。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 設(shè)圖 是圖 G=(V , E )的一支撐子圖， 如果圖 是一個(gè)樹 ,那么稱 K 是 G 的一個(gè)生成樹（支撐樹），或簡(jiǎn)稱為圖 G 的樹。 （ 3） 樹 中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。 v1 v2 v3 v4 v5 v6 一個(gè)連通的無(wú)圈的無(wú)向圖叫做樹。若鏈中所含的邊均不相同，則稱此鏈為簡(jiǎn)單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈 , 也稱通路。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 有向圖中 ， 以 vi 為始點(diǎn)的邊數(shù)稱為點(diǎn) vi的出次 ， 用 表示 ；以 vi 為終點(diǎn)的邊數(shù)稱為點(diǎn) vi 的入次 ， 用 表示； vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次 。 以點(diǎn) v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn) v 的度（次），記作 。 有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。 v4 v6 v1 v2 v3 v5 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 圖 2 一條邊的兩個(gè)端點(diǎn)是相同的 ,那么稱為這條邊是環(huán)。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個(gè)圖是由點(diǎn)集 和 中元素的無(wú)序?qū)Φ囊粋€(gè)集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點(diǎn) ， V 表示圖 G 的點(diǎn)集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得到第一次就座方案是（ 1， 2， 3， 4，5， 6， 7， 1），繼續(xù)尋求第二次就座方案時(shí)就不允許這些頂點(diǎn)之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。 有 7個(gè)人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問(wèn)不同的就座方案共有多少種 ？ 用頂點(diǎn)表示人 ， 用邊表示兩者相鄰 ， 因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰 ， 所以任何兩點(diǎn)都可以有邊相連 。 1 2 3 7 6 4 5 引論 圖的用處 某公司的 組織機(jī)構(gòu)設(shè)置圖 總公司 分公司 工廠或辦事處 一、 圖與網(wǎng)絡(luò)的基本知識(shí) （一）、 圖與網(wǎng)絡(luò)的基本概念 E A D C B 一個(gè)圖是由點(diǎn)和連線組成。一條方向從 vi指向 vj 的弧，記作 (vi , vj)。 每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為完全圖。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。 所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。對(duì)每一條弧 ，對(duì)應(yīng)一個(gè)數(shù) ，稱為弧上的 “ 權(quán) ” 。 其鏈長(zhǎng)為 n ， 其中 v0 ， vn 分別稱為鏈的起點(diǎn)和終點(diǎn) 。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB?????????????????????例 權(quán)矩陣為： 鄰接矩陣為： v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321654321 030303302021020576305020007204346040vvvvvvvvvvvvA????????????????????? 二 、 樹及最小樹問(wèn)題 已知有六個(gè)城市 ， 它們之間 要架設(shè)電話線 ， 要求任意兩個(gè)城市均可以互相通話 ， 并且電話線的總長(zhǎng)度最短 。 （ 2） n 個(gè)頂點(diǎn)的樹必有 n1 條邊 。 v1 v2 v3 v4 v5 v6 一個(gè)圖 G 有生成樹的充要條件是 G 是連通圖。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。 最小生成樹問(wèn)題 一棵生成樹所有樹枝上權(quán)的總和為這個(gè)生成樹的權(quán) 。 在余下的圖中重復(fù)這個(gè)步驟 ，直到得到一不含圈的圖為止 。即： 最小。對(duì) vj的 T標(biāo)號(hào)進(jìn)行如下修改： T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為 P標(biāo)號(hào)，即： 當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為 P標(biāo)號(hào)。 0)( 1 ?vP )6,3,2()( ????? ivT i（ 2） （ 3) 3]30,m i n [])(,)(m i n [)( 12122 ??????? lvPvTvT5]50,m i n [])(,)(m i n [)( 13133 ??????? lvPvTvT3)( 2 ?vP（ 4） 4]13,5m i n [])(,)(m i n [)(23233 ????? lvPvTvT5]23,m i n [])(,)(m i n [)( 24244 ??????? lvPvTvT5]23,m i n [])(,)(m i n [)( 25255 ??????? lvPvTvTv1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 ?vP（ 5） （ 6） 8]44,6m i n [])(,)(m i n [)(35355 ????? lvPvTvT5)( 4 ?vP 5)( 5 ?vP9]45,m i n [])(,)(m i n [)( 46466 ??????? lvPvTvT7]25,m i n [])(,)(m i n [)( 56566 ??????? lvPvTvT7)( 6 ?vP（ 7） （ 8） （ 9） （ 10） 反向追蹤得 v1到 v6的最短路為： 6521 vvvv ???2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 練習(xí) \作業(yè) :求從 1到 8的最短路徑 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1 p4=1 p1=0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2 p1=0 p4=1 p2=2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c13,c23,c25,c47}=min {0+3,2+6,2+5,