離散數(shù)學(xué)課件圖論(3)-資料下載頁(yè)
2025-01-16 20:24本頁(yè)面
【正文】 A∨ A(2)∨ A(3)∨ A(4)∨ A(5) )2()4()3()2()1(1001001000101101101001001 ,0100000010010011101010110 ,1001001000101101101001001 ,0100010010010010100000100AAAAA ??????????????????????????????????????????????????????????????????????????????????????1101011010111111101011111P144 圖的矩陣表示 補(bǔ)充知識(shí) : 強(qiáng)分圖、單側(cè)分圖和弱分圖 在簡(jiǎn)單有向圖中 ,具有強(qiáng)連通的最大子圖 ,稱為 強(qiáng)分圖 .具 有單側(cè)連通的最大子圖 ,稱為 單側(cè)分圖 . 具有弱連通的最 大子圖 ,稱為 弱分圖 . 這些 分圖用結(jié)點(diǎn)的集合表示 . 例如 ,給定有向圖 G,如圖所示 : 求它的強(qiáng)分圖、單側(cè)分圖和 弱分圖 . 解 : 強(qiáng)分圖 :由 {a,g,h}{c} nhcuj7d3{e}{f}導(dǎo)出的子圖 . 單側(cè)分圖 :由 {a,g,h,b,f,d,e}{b,c,f,d,e}導(dǎo)出的子圖 . 弱分圖 :G本身是弱分圖 . 在有向圖中 ,每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中 ?e f? c? ?d ?g h? a? ?b School of Information Science and Engineering 144 圖的矩陣表示 ［用可達(dá)矩陣求強(qiáng)分圖］ 下面看怎樣用 P求強(qiáng)分圖 ? 先將 P轉(zhuǎn)置得 PT, 如果 vi與vj相互可達(dá) ,則 pij= pTij =1 ? 以 G2為例說(shuō)明。 11111 01011 11111 01011 01011 P= 10100 11111 10100 11111 11111 PT= P∧ PT= 10100 01011 10100 01011 01011 11000 11000 00111 00111 00111 初等 變換 得 v1v3 v2v4v5 ? 對(duì) P∧ PT進(jìn)行初等變換 , 第 2行與第 3行交換 ,再第 2列與第 3 列交換 , 最后得兩個(gè)強(qiáng)分圖： {v1,v3}和 {v2,v4,v5} G2v 1v 3v 4v 5v 2 School of Information Science and Engineering 144 圖的矩陣表示 3. 關(guān)聯(lián)矩陣 ① 無(wú)向圖的完全關(guān)聯(lián)矩陣 ［定義］ 設(shè) G=V, E是個(gè)無(wú)向圖， V={v1, v2, v3, …, vm }, E={e1, e2, e3, …, en },一個(gè) m n階矩陣 M=(mij)稱為 G的關(guān)聯(lián)矩陣 。 其中 : mij為 頂點(diǎn) vi與邊 ej的關(guān)聯(lián)次數(shù) 平行邊的列相同)4(2)3(), .. . ,2,1()()2(), .. . ,2,1(2)1(,11mmnivdmmjmjiijimj ijni ij??????????［性質(zhì)］ v 1v 2v 3v 4v 5e 1e 2e 3e 4e 5e 6e 7?????????????????11000001010000010111000111010000011M School of Information Science and Engineering 144 圖的矩陣表示 ② 有向圖的完全關(guān)聯(lián)矩陣 ［定義］ 設(shè) G=V,E是個(gè)有向圖，且無(wú)環(huán) ,V={v1,v2,v3,…, vm }, E={e1,e2,e3,…, en },一個(gè) m n階矩陣 M=(mij)稱為 G的完全 關(guān)聯(lián)矩陣。 其中 : vi是 ej的起點(diǎn) vi是 ej的終點(diǎn) vi與 ej不關(guān)聯(lián) ???????011ijm［性質(zhì)］ ?? ???????????? ????jiijmjmj iijiijni ijmnivdmvdmmjm,1 110)3(, . . . ,2,1),()1(),()1()2(), . . . ,2,1(0)1((4) 平行邊對(duì)應(yīng)的列相同 School of Information Science and Engineering 主要內(nèi)容 ? 無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu) ? 通路與回路及其分類 ? 無(wú)向圖的連通性與連通度 ? 有向圖的連通性及其分類 ? 圖的矩陣表示 主要內(nèi)容 School of Information Science and Engineering 練習(xí) 1． 9階無(wú)向圖 G中，每個(gè)頂點(diǎn)的度數(shù)不是 5就是 6. 證明 G中至少有 5個(gè) 6度頂點(diǎn)或至少有 6個(gè) 5度頂點(diǎn) . 2．?dāng)?shù)組 2, 2, 2, 2, 3, 3能簡(jiǎn)單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來(lái) . School of Information Science and Engineering 練習(xí) 3．有向圖 D如圖所示，回答下列問(wèn)題： (1) D中有幾種非同構(gòu)的圈？ (2) D中有幾種非圈非同構(gòu)的簡(jiǎn)單回路？ (3) D是哪類連通圖 ? (4) D中 v1到 v4長(zhǎng)度為 1,2,3,4的通路各多少 條？其中幾條是非初級(jí)的簡(jiǎn)單通路？ (5) D中 v1到 v1長(zhǎng)度為 1,2,3,4的回路各多少 條？討論它們的類型 . (6) D中長(zhǎng)度為 4的通路（不含回路）有多少條？ (7) D中長(zhǎng)度為 4的回路有多少條？ (8) D中長(zhǎng)度 ?4的通路有多少條？其中有幾條是回路？ (9) 寫出 D的可達(dá)矩陣 .
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1