離散數(shù)學課件圖論(2)-資料下載頁
2025-01-16 20:45本頁面
【正文】 144 圖的矩陣表示 School of Information Science and Engineering 例： G2如圖所示 , 求它的 可達矩陣 P。 G2v 1v 3v 4v 5v 2P=A∨ A(2)∨ A(3)∨ A(4)∨ A(5) )2()4()3()2()1(1001001000101101101001001 ,0100000010010011101010110 ,1001001000101101101001001 ,0100010010010010100000100AAAAA ??????????????????????????????????????????????????????????????????????????????????????1101011010111111101011111P144 圖的矩陣表示 School of Information Science and Engineering 144 圖的矩陣表示 ［用可達矩陣求強分圖］ 下面看怎樣用 P求強分圖 ? 先將 P轉(zhuǎn)置得 PT, 如果 vi與vj相互可達 ,則 pij= pTij =1 ? 以 G2為例說明。 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 ? 對 P∧ PT進行初等變換 , 第 2行與第 3行交換 ,再第 2列與第 3 列交換 , 最后得兩個強分圖： {v1,v3}和 {v2,v4,v5} G2v 1v 3v 4v 5v 2 School of Information Science and Engineering 144 圖的矩陣表示 3. 關(guān)聯(lián)矩陣 ① 無向圖的完全關(guān)聯(lián)矩陣 ［定義］ 設(shè) G=V, E是個無向圖， V={v1, v2, v3, …, vm }, E={e1, e2, e3, …, en },一個 m n階矩陣 M=(mij) 稱為 G的關(guān)聯(lián)矩陣 。 其中 : vi到 ej關(guān)聯(lián) 否則 ????0 1 ijm平行邊的列相同)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是個簡單有向圖， V={v1,v2,v3,…, vm }, E={e1,e2,e3,…, en },一個 m n階矩陣 M=(mij)稱為 G的完全 關(guān)聯(lián)矩陣。 其中 : vi是 ej的起點 vi是 ej的終點 vi與 ej不關(guān)聯(lián) ???????011ijm［性質(zhì)］ ?? ???????????? ????jiijmjmj iijiijni ijmnivdmvdmmjm,1 110)3(, . . . ,2,1),()1(),()1()2(), . . . ,2,1(0)1((4) 平行邊對應(yīng)的列相同 School of Information Science and Engineering 例： 有向圖 D如圖所示，求 A, A2, A3, A4，并回答諸問題： (1) D 中長度為 1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長度小于或等于 4的通路為多少條？其中有多少條回路？ 實例 School of Information Science and Engineering School of Information Science and Engineering ????????????????????????????????????????????????????1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長度為 1的通路為 8條，其中有 1條是回路。 D中長度為 2的通路為 11條，其中有 3條是回路。 D中長度為 3和 4的通路分別為 14和 17條，回路分別為 1與3條。 (2) D中長度小于等于 4的通路為 50條，其中有 8條是回路。 求解 School of Information Science and Engineering 主要內(nèi)容 ? 無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖；握手定理與推論；圖的同構(gòu) ? 通路與回路及其分類 ? 無向圖的連通性與連通度 ? 有向圖的連通性及其分類 ? 圖的矩陣表示 主要內(nèi)容
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1