《離散數(shù)學(xué)》ppt課件(文件)
【正文】 可達(dá)的。 離散數(shù)學(xué) 35 在 (a)中有： d(v2， v1)＝ d(v1， v2)＝ d(v3， v1)＝ d(v1， v3)＝ 在 (b)中有： d(v1， v3)＝， d(v3， v7)＝， d(v1， v7)＝。 “ ?” G是強連通圖，則任意兩個結(jié)點之間都是相互可達(dá)的，設(shè) G＝ V， E， V＝ {v1,v２ ,v３ ,… ,vｎ }，則 v1到 v2可達(dá)，v2到 v3可達(dá)， v3到 v4可達(dá)， …… ， vｎ １ 到 vｎ 可達(dá)， vn到 v1可達(dá)，由此可得到一條回路 (v1， v２ ， v３ ， …… ， vｎ ， v1)，它至少包含每個結(jié)點一次。 離散數(shù)學(xué) 42 定理 ? 在有向圖 G＝ V， E，它的每一個結(jié)點必然位于且僅位于一個強分圖中； ? 在有向圖 G＝ V， E，它的每一個結(jié)點和每一條邊都至少位于一個單向分圖中； ? 在有向圖 G＝ V， E，它的每一個結(jié)點和每一條邊必然位于且僅位于一個弱分圖中。 例： 離散數(shù)學(xué) 45 73 圖的矩陣表示 一、 鄰接矩陣 設(shè) G＝ V,E是一個簡單圖， V＝ {v1,v2,… ,vn}， E＝{e1,e2,… ,en}，則 n階方陣 A(G)＝ (aij)n?n稱為 G的 鄰接矩陣 。＝ A A＝ (aij(2))n?n，則有： ????n1kkjik)2(ijij aaab此時， bij表示從 vi到 vj長度為 2的路數(shù)目，如 bij＝ 0，則無長度為 2的路，而 bii給出了經(jīng)過 vi的長度為 2的回路數(shù)目； 7) 令 C＝ (cij)＝ Am＝ A A … A＝ (aij(m))n?n，則有： ?????? ???n1kkj)1m(n1k)1m(ik)m(ij aaaaac ikkjij此時， cij表示從 vi到 vj長度為 m的數(shù)目，如 cij＝ 0，則無長度為 m的路，而 cii給出了經(jīng)過 vi的長度為 m的回路數(shù)目。 對所有的 k求和 ， 即是所有從 vi到 v的長度為 t+1的路的數(shù)目 ， 故命題對成立 。，????????????????????????????????????????????????????????????3303330300903303A0030003033030030A1101110100301101A0010001011010010A432如下： 上面圖中結(jié)點的度數(shù)和兩結(jié)點間長度為 k的路的條數(shù)。 見例題 1。???????????????1111111111111111P離散數(shù)學(xué) 56 利用布爾求乘和布爾求和的運算直接求可達(dá)性矩陣 P＝ A?A(2)?A(3)?...?A(n) A(m)＝ A?A?A?...?A (m＝ 1,2,3,… n) 若把鄰接矩陣看作是結(jié)點集 V上關(guān)系 R的關(guān)系矩陣，則可達(dá)性矩陣 P即為 MR＋ ， 因此可達(dá)性矩陣可以用 Warshall算法計算 2) 利用布爾求乘和布爾求和的運算直接求可達(dá)性矩陣 離散數(shù)學(xué) 57 例： 例： 利用鄰接矩陣的布爾運算求可達(dá)性矩陣。 ⑵每一行元素的和數(shù)對應(yīng)于 。 離散數(shù)學(xué) 61 定義 定義 給定簡單有向圖 G=〈 V ， E〉 ， V={v1,v2,… vp} ， E={e1,e2,… eq} ，p q階矩陣 M(G)=(mij)， 其中 稱 M(G)為 G的完全關(guān)聯(lián)矩陣 。 離散數(shù)學(xué) 63 例： 例： 如對于圖，可寫完全關(guān)聯(lián)矩陣： 離散數(shù)學(xué) 64 邊的合并 對圖 G的完全關(guān)聯(lián)矩陣中的兩個行相加定義如下： 若記 vi對應(yīng)的行為 ， 將第 i行與第 j行相加 ， 規(guī)定 為：對有向圖是指對應(yīng)分量的加法運算 ， 對無向圖是 指對應(yīng)分量的模 2的加法運算 ， 把這種運算記作 iv?ijji vvv ??? ??離散數(shù)學(xué) 65 邊的合并 關(guān)聯(lián)矩陣的加法運算 例： 圖 (a)中使 v4和 v5合并得到圖 (b)。 b) vi與 vj都是邊 er的端點 ， 那么合并后在 G’中 er成為 vi,j的自回路 ， 按規(guī)定應(yīng)該被刪去 。 ⑵ 設(shè) M(G)的第一列對應(yīng)邊 e， 且 e的端點為 vi和 vj， 調(diào)整行序使第 i行為第一行 ， 這時 M(G)的首列僅在第 1行和第 j行為 1， 其余各元素均為 0， 再把第一行加到第 j行上去則得到矩陣 M’(G)。 如果 M’(G1)的第一列全為零 ， 則可將 M’(G1)的非零列與第一列對調(diào) ， 不影響完全關(guān)聯(lián)矩陣的秩數(shù) 。 離散數(shù)學(xué) 71 矩陣與圖的連通性 矩陣與圖的連通性 無向線圖 G是連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣 P的所有元素都 均為 1； 有向線圖 G是強連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣 P的所有元素 都均為 1； 有向線圖 G是單側(cè)連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣 P及其轉(zhuǎn)置 矩陣 PT經(jīng) “ 布爾求和 ” 運算后所得矩陣 P1＝ P∨P T中除對角線以 外的其余元素均為 1； 有向線圖 G是弱連通圖當(dāng)且僅當(dāng)它的鄰接矩陣 A及其轉(zhuǎn)置矩陣 AT經(jīng) “ 布爾求和 ” 運算后作為新的鄰接矩陣 B＝ A∨A T而求出的可 達(dá)性矩陣 PB中所有元素均為 1。 顯然 M(r1)(G)有一個 (r1)階子陣 ， 其行列式的值不為 0， 故 M(r1)(G)的秩至少為 r1。 離散數(shù)學(xué) 68 證明 離散數(shù)學(xué) 69 證明（續(xù)） 證明 由于 M’(G1)是 G1的完全關(guān)聯(lián)矩陣 ， 而 G1是由 G的兩個結(jié)點 vi和 vj合并而得到 。 證明 這里對無向圖進(jìn)行證明 。 因為若有 關(guān)項中第 r個對應(yīng)分量有 ， 則說明 vi與 vj兩者之中只有一個結(jié)點是邊 er的端點 ， 且將這兩 個結(jié)點合并后的結(jié)點 vi,j仍是 er的端點 。 ⑵每一行元素 ” 1”的個數(shù)對應(yīng)于 ， ” 1”的個數(shù)對應(yīng)于 。 ⑷兩個平行邊其對應(yīng)的兩列相同。）（）（）（????????????????????1111111111111111A......AAAP n32離散數(shù)學(xué) 58 三：完全關(guān)聯(lián)矩陣 三：完全關(guān)聯(lián)矩陣 定義 給定無向圖 G， 令 v1,v2,… ,vp和 e1,e2,… ,eq分別記為 G的結(jié)點和邊 ， 則矩陣 M
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1