歐拉圖與漢密爾頓ppt課件(編輯修改稿)
2025-05-29 18:03 本頁面
【文章內(nèi)容簡介】 ? 每列和為入度 : ?ni=1aij=d(vj) ? 握手定理 : ?ni=1?nj=1aij=?ni=1d(vj)=m ? 環(huán)個數(shù) : ?ni=1aii v1 v2 v4 v3 ?????????????1100100001000120)(43214321vvvvvvvvDA18 鄰接矩陣與通路數(shù) ? 設(shè) A(D)=A=[aij]n?n, ? Ar=Ar1?A (r?2), Ar=[aij(r)]n?n, ? 定理 2: aij(r)=從 vi到 vj長度為 r的通路總數(shù) ? ?ni=1?nj=1aij(r)=長度為 r的通路總數(shù) ? ?ni=1aii (r) =長度為 r的回路總數(shù) 19 用鄰接矩陣求通路數(shù) (例 ) v1 v2 v4 v3 ?????????????1100100001000120)(43214321vvvvvvvvDA?????????????21001100100012002A?????????????32002100110031003A?????????????53003200210043004A?????????????32002100110013202B?????????????64004200220044203B?????????????117007400430087204B20 可達(dá)矩陣 ? 設(shè) D=V,E是有向圖 ,V={v1,v2,… ,vn}, ? 可達(dá)矩陣 : P(D)=[pij]n?n, 1, 從 vi可達(dá) vj pij = 0, 從 vi不可達(dá) vj 21 可達(dá)矩陣 (性質(zhì) ) ? 主對角線元素都是 1: ?vi?V, 從 vi可達(dá) vi ? 強(qiáng)連通圖 : 所有元素都是 1 ? 偽對角陣 : 對角塊是強(qiáng)連通分支的可達(dá)矩陣 ? ?i?j, pij=1 ? bij (n1) 0 ?????????????)()()()(21kDPDPDPDP?22 圖的運算 ? 定義 設(shè)圖 G1=V1， E1, G2=V2， E2,若 V1∩V 2= ?， 則稱 G1與 G2 是 不交的 . 若 E1∩E 2= ?，則稱 E1與 E2 是 不重的 . 由定義知，不交的圖必然是邊不交的，但反之 不真。 23 圖的運算 ? 定義 設(shè)圖 G1=V1， E1, G2=V2， E2為不含孤立點的 兩個圖（它們同為無向圖或同為有向圖 ). (1)稱以 V1∪V 2為頂點集，以 E1∪E 2 為邊集的圖為 G1與 G2 的并圖 ,記作 G1∪G 2 ,即 G1∪G 2 = V1∪V 2 ,E1∪E 2 . 24 圖的運算 (2)稱以 E1 E2為邊集 ,以 E1 E2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為 G1與 G2的 差圖 ,記作 G1 G2. (3)稱以 E1∩E 2為邊集 ,以 E1∩E 2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為 G1與 G2的 交圖 ,記作 G1∩G 2. (4)稱以 E1⊕E 2為邊集 ,以 E1⊕E 2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為 G1與 G2的 交圖 ,記作 G1⊕G 2. 25 圖的運算 在定義 ： G1= G2,則 G1∪G 2= G1∩G 2= G1(G2),而 G1G2= G2G1 = ?,這就是在圖的定義中給出空圖的概念的原因 . G1與 G2邊不重時 ,G1∩G 2 = ?, G1G2= G1,G1⊕G 2 = G1∪G 2. 、交、差給出 :
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1