離散數(shù)學(xué)課件第5章(1)(參考版)
2025-01-19 20:38本頁面
【正文】 ? Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree. 應(yīng)用兩圖中相應(yīng)頂點具有相同的度來判斷兩圖的同構(gòu)情況 (2) We can also use paths to find mapping that are potential isomorphisms. 52 2022/2/13 Connectivity 〖 Example 3〗 Are these two graphs isomorphic? Solution: No. Because the right graph contains circuits of length 3, while the left graph does not. 53 2022/2/13 Connectivity Homework: P. 476 18（ b,c） , 20 本節(jié)內(nèi)容到此結(jié)束 。 同理，把一旦刪除就產(chǎn)生帶有比原圖更多的連通分支的子圖的邊稱為 割邊或橋 For example, （ 1） In the star work the center vertex is a cut vertex. All edges are cut ，其中所有的邊都是割邊 49 2022/2/13 Connectivity （ 2） There are no cut edges or vertices in the graph G above. Removal of any vertex or edge does not create additional ponents. 50 2022/2/13 Connectivity Connectedness in directed graphs 有向圖的連通性 強連通的 ：若每當 a和 b都是一個有向圖里的頂點時，就有從 a到 b和從 b到 a的通路 . 弱連通的 ：若在有向圖的底圖里，任何兩個頂點之間都有通路 由定義可知：任何強連通有向圖也是弱連通的。把這樣的頂點稱為 割點（或節(jié)點） 。刪除所有冗余的回路使得通路更短。 每個連通分量均有極大連通子圖。 1 (2) The number of paths not exceeding 6 are there from v4 to v5? a45 in A+A2+A3+A4+A5+A6 。 從 vi到 vj的長度為 r的不同通路的數(shù)目等于 Ar的第（ i,j)項，其 中 r是正整數(shù)。A ＝ 1 1 2 0 2 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 2 1 4 1 2 2 1 2 3 0 2 1 5 2 0 0 1 0 0 1 0 0 1 0 0 0 1 1 2A ＝ 3A )( )3(ija＝ )(kija其中： ＝ ???71)1(hhjkih aa現(xiàn)在來看看 的值有什么實際意義。 如果我們進一步問：若 v1城到 v7有道路相通，共有幾條不同的道路？ v1 v2 v3 v4 v5 v6 v7 A＝ 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 考察鄰接矩陣： A v1 v2 v3 v4 v6 v5 v7 v8 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 μ={v1 e2 v3 e5 v4}是一條道路 若圖 G中的 μ所有邊均不相同 —— 簡單道路； 若道路 μ中 v0=vk(即首尾相同 )—— 回路； 若回路 μ中沒有重復(fù)邊 —— 簡單回路。 然而，可以通過說明兩個簡單圖不具有同構(gòu)的圖所必須具有的性質(zhì)來說明 它們不同構(gòu)。 如何判斷兩圖同構(gòu)是圖論中一個困難問題。 (a) d‘(d) ?圖的同構(gòu) 1 v1 v2 v3 v4 圖 G1 va vb vc vd 圖 G2 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A1＝ 1 2 3 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A2＝ a b c d v1va v2vb v3vc v4vd 判別定理：圖 G1 ， G2同構(gòu)的 充要條件 是：存在置換矩陣 P，使得： A1＝ PA2P。 (c) a39。這樣的函數(shù) f 稱為 同構(gòu) . 換句話說，當兩個簡單圖同構(gòu)時，兩個圖的頂點之間具有保持鄰接關(guān)系的一一對應(yīng)。 dij=∑αik αjk vi vj vk 22 2022/2/13 Representing Graphs and Graph Isomorphism Incidence matrices 關(guān)聯(lián)矩陣 設(shè) G = (V, E) 是無向圖 .設(shè) . 是頂點而 是邊 。 cij=∑αik αjk vi vj vk (5) 有向圖中： D=ATA。 a11 a12 … a 1n a21 a22 … a 2n …… an1 an2 … a nn B=A2= a11 a12 … a 1n a21 a22 … a 2n …… an1 an2 … a nn ＝ (bij)n n bij表示 vi兩步到達 vj的路徑數(shù)目 (4) 有向圖中： C=AAT。 (無向圖 ) v4 v1 v2 v3
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1