離散數(shù)學課件-第5章-3、4

1、1離散數(shù)學Discrete Mathematics 汪榮貴汪榮貴 教授教授合肥工業(yè)大學軟件學院專用課件合肥工業(yè)大學軟件學院專用課件2011.06graph theory 3 42022-3-205.3 Representing Graphs and Graph Isomorphism 圖的表示Methods for representing graphs:n Adjacency lists 鄰接表 - lists that specify all the vertices that are adjacent to each vertex該表規(guī)定與圖的每個頂點鄰接的頂點該表規(guī)定與圖的每個頂點鄰接

2、的頂點n Adjacency matrice 鄰接矩陣鄰接矩陣n Incidence matrices 關聯(lián)矩陣關聯(lián)矩陣52022-3-20Adjacency lists鄰接表鄰接表例：例： 用鄰接表描述所給的簡單圖用鄰接表描述所給的簡單圖62022-3-20 若圖里面有許多邊，則把圖表示成邊表或鄰接表，若圖里面有許多邊，則把圖表示成邊表或鄰接表，就不便于執(zhí)行圖的算法。就不便于執(zhí)行圖的算法。 為了簡化計算，可用矩陣表示圖。在這里將給出為了簡化計算，可用矩陣表示圖。在這里將給出兩種類型的常用的表示圖的矩陣兩種類型的常用的表示圖的矩陣: 一種類型是基于頂點的鄰接關系，一種類型是基于頂點的鄰接關系，

3、 一種類型是基于頂點與邊的關聯(lián)關系一種類型是基于頂點與邊的關聯(lián)關系。72022-3-205.3 Representing Graphs and Graph Isomorphism 定義：假設定義：假設 G = (V, E)是簡單圖是簡單圖 ，其中，其中 | V | = n . 假 設 把假 設 把 G 的 頂 點 任 意 地 排 列的 頂 點 任 意 地 排 列成成 。對這個頂點表來說，。對這個頂點表來說，G的鄰的鄰接矩陣接矩陣A是一個是一個nn的的01矩陣，它滿足這矩陣，它滿足這樣的性質(zhì)樣的性質(zhì)nvvv,21aij = 1 if vi, vj is an edge of G,aij = 0o

4、therwise.82022-3-20Example 1 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?0111100110011110GASolution:Note: Adjacency matrices of undirected graphs are always symmetric.無向圖的鄰接矩陣總無向圖的鄰接矩陣總是對稱的是對稱的5.3 Representing Graphs and Graph Isomorphism 9202

5、2-3-20注意：注意： 1） 圖的鄰接矩陣依賴于所選擇的頂點的順序。因圖的鄰接矩陣依賴于所選擇的頂點的順序。因此帶此帶n個頂點的圖有個頂點的圖有n!個不同的鄰接矩陣，因為個不同的鄰接矩陣，因為n個個頂點有頂點有n!個不同的順序。個不同的順序。 2） 當圖里的邊相對少時，鄰接矩陣是稀疏矩陣，當圖里的邊相對少時，鄰接矩陣是稀疏矩陣，即只有很少的非即只有很少的非0項的矩陣?？梢杂锰厥獾姆椒▉肀眄椀木仃?。可以用特殊的方法來表示和計算這樣的矩陣。示和計算這樣的矩陣。102022-3-205.3 Representing Graphs and Graph Isomorphism Example 2 Wh

6、at is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?Solution:Note: For undirected multigraph or pseudograph , adjacency matrices are symmetric.無向無向多重圖與偽多重圖與偽圖都具有對稱的鄰接矩陣圖都具有對稱的鄰接矩陣0312300110112110GA112022-3-205.3 Representing Graphs and Graph Isomorphism

7、 The adjacency matrix of a directed graph有向圖的鄰接矩陣有向圖的鄰接矩陣 Let G = (V, E) be a directed graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, , vn. 假設假設G=(V,E)是含是含n個頂點的有向圖。若個頂點的有向圖。若 是有向圖是有向圖任意的頂點序列。任意的頂點序列。 The adjacency matrix A (or AG) of G, with respect to th

8、is listing of the vertices, is the n n zero-one matrix with 1 as its (i, j)th entry when there is an edge from vi to vj, and 0 otherwise.若有向圖若有向圖G=(V,E)從從 有邊，則它的矩陣在（有邊，則它的矩陣在（i,j）位置上有位置上有1，否則為，否則為0In other words, for an adjacency matrix A = aij, aij = 1 if (vi, vj) is an edge of G, aij = 0 otherwise

9、.12, ,.,nv vvijv 到 v122022-3-205.3 Representing Graphs and Graph Isomorphism Example 3 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?Solution:0111000000010100GA132022-3-205.3 Representing Graphs and Graph Isomorphism Question:1. What is the sum

10、of the entries in a row of the adjacency matrix for an undirected graph? 對無向圖來說，鄰接矩陣每一行各個位置上數(shù)字之和代表什對無向圖來說，鄰接矩陣每一行各個位置上數(shù)字之和代表什么？么？0312300110112110GA142022-3-205.3 Representing Graphs and Graph Isomorphism Question:1. What is the sum of the entries in a row of the adjacency matrix for an undirected gr

11、aph?對無向圖來說，鄰接矩陣每一對無向圖來說，鄰接矩陣每一行各個位置上數(shù)字之和代表什么？行各個位置上數(shù)字之和代表什么？ The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. 與與頂點頂點i關聯(lián)的邊數(shù)等于頂點關聯(lián)的邊數(shù)等于頂點i的度減去在頂點的度減去在頂點i上的環(huán)數(shù)上的環(huán)數(shù) For a directed graph?0111000000010100GA152022-3-205.3 Representing Graphs and

12、Graph Isomorphism Question:1. What is the sum of the entries in a row of the adjacency matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?對于有向圖而言對于有向圖而言，鄰接矩陣每一行各個位置上鄰接矩陣每一行各個位置上數(shù)字之和代表什么？代

13、表該頂點的出度數(shù)字之和代表什么？代表該頂點的出度 deg+(vi) 2. What is the sum of the entries in a column of the adjacency matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?對于有向圖而言對于有向圖而言，鄰接矩陣每一列各個位置上鄰接矩陣每一列各個位置上

14、數(shù)字之和代表什么？代表該頂點的入度數(shù)字之和代表什么？代表該頂點的入度deg-(vi) 置換矩陣：相當于將單位矩陣中相應的行與行，置換矩陣：相當于將單位矩陣中相應的行與行，或者列與列互換的矩陣?；蛘吡信c列互換的矩陣。1 0 00 0 10 1 0P a11 a12 a13a21 a22 a23 a31 a32 a33 A a11 a12 a13a31 a32 a33a21 a22 a23PA a11 a13 a12a31 a33 a32a21 a23 a22(PA)P P就是一個置換矩陣鄰接矩陣中圖的性質(zhì)：鄰接矩陣中圖的性質(zhì)：v1v2v3v40 1 1 01 0 1 11 1 0 00 1 0

15、0A 無向圖的鄰接矩陣是對稱的！(1)A=(ij)nn中，第i行或第i列中非0元素的個數(shù)等于頂點vi的度。(無向圖無向圖)v4v1v2v30 1 1 00 0 0 10 1 0 11 0 1 0A 豎入橫出(2) A=(ij)nn中，第中，第i列列中非中非0元素的個數(shù)等于頂點元素的個數(shù)等于頂點vi的的入入度，第度，第i行行中非中非0元素的個數(shù)等于頂點元素的個數(shù)等于頂點vi的的出出度。度。(有向圖有向圖)(3) B=A2。a11 a12 a1na21 a22 a2n an1 an2 ann B=A2=a11 a12 a1na21 a22 a2n an1 an2 ann (bij)nnbij表示v

16、i兩步到達vj的路徑數(shù)目(4) 有向圖中：C=AAT。a11 a12 a1na21 a22 a2n an1 an2 ann C= (cij)=a11 a21 an1a12 a22 an2 a1n a2n ann cij表示以vi,vj為始始點的終終點數(shù)目。cij=ik jkvivjvk(5) 有向圖中：有向圖中：D=ATA。a11 a12 a1na21 a22 a2n an1 an2 ann D= (cij)=a11 a21 an1a12 a22 an2 a1n a2n ann dij表示以vi,vj為終終點的始始點數(shù)目。dij=ik jkvivjvk222022-3-205.3 Repres

17、enting Graphs and Graph Isomorphism 設設 G = (V, E) 是無向圖是無向圖.設設. 是頂點而是頂點而是邊。則相對于是邊。則相對于V和和E的這個順序的關聯(lián)矩陣是的這個順序的關聯(lián)矩陣是nm矩陣矩陣nvvv,21meee,21mnijmMotherwise0 ith incident w is edgewhen 1ijijvem232022-3-205.3 Representing Graphs and Graph Isomorphism Example 4 What is the incidence matrix M for the following g

18、raph G based on the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6?Solution:001110111000000101010011dcbaMNote:Incidence matrices of undirected graphs contain two 1s per column for edges connecting two vertices and one 1 per column for loops.在無向圖中的關聯(lián)矩陣中，每列在無向圖中的關聯(lián)矩陣中，每列中有兩個中有兩個1的表明這條邊與的表明這條邊

19、與這兩個頂點相連接，每列有這兩個頂點相連接，每列有一個一個1的表明存在環(huán)的表明存在環(huán)242022-3-205.3 Representing Graphs and Graph Isomorphism 定義：設定義：設G1= (V1, E1) 和和G2= (V2, E2)是簡單圖，若存在一對是簡單圖，若存在一對一的和映上的從一的和映上的從 V1 到到V2 的函數(shù)的函數(shù)f，且，且f具有這樣的性質(zhì)，具有這樣的性質(zhì)，對對V1里所有的里所有的a 和和 b來說，來說，a和和b在在 G1里鄰接，當且僅當里鄰接，當且僅當 f(a)和和 f(b)在在 G2里鄰接，就說里鄰接，就說G1和和G2是同構(gòu)的。這樣的是同構(gòu)

20、的。這樣的函數(shù)函數(shù) f 稱為稱為同構(gòu)同構(gòu). 換句話說，當兩個簡單圖同構(gòu)時，兩個圖的頂點之間具換句話說，當兩個簡單圖同構(gòu)時，兩個圖的頂點之間具有保持鄰接關系的一一對應。有保持鄰接關系的一一對應。For example,adcbb (c)a (b)c (a)d(d)v1v2v3v4圖G1vavbvcvd圖G20 1 1 11 0 1 11 1 0 11 1 1 0A11 2 3 40 1 1 11 0 1 11 1 0 11 1 1 0A2a b c dv1vav2vbv3vcv4vd判別定理：圖判別定理：圖G1 ，G2同構(gòu)的同構(gòu)的充要條件充要條件是：存在置換是：存在置換矩陣矩陣P，使得：，使得：

21、A1PA2P。 其中其中A1，A2分別是分別是G1 ，G2的鄰接矩陣。的鄰接矩陣。如何判斷兩圖同構(gòu)是圖論中一個困難問題。如何判斷兩圖同構(gòu)是圖論中一個困難問題。272022-3-205.3 Representing Graphs and Graph Isomorphism Question: 怎么判斷兩個簡單圖是否同構(gòu)怎么判斷兩個簡單圖是否同構(gòu)? 在兩個帶在兩個帶n個頂點的簡單圖頂點集之間有個頂點的簡單圖頂點集之間有n！種可能的！種可能的一一對應，通過檢驗每一種對應來看它是否保持鄰接關系一一對應，通過檢驗每一種對應來看它是否保持鄰接關系和不鄰接關系是不可行的。和不鄰接關系是不可行的。 然而，可以

22、通過說明兩個簡單圖不具有同構(gòu)的圖所必然而，可以通過說明兩個簡單圖不具有同構(gòu)的圖所必須具有的性質(zhì)來說明須具有的性質(zhì)來說明 它們不同構(gòu)。把這樣的性質(zhì)稱為對它們不同構(gòu)。把這樣的性質(zhì)稱為對簡單圖的同構(gòu)來說的不變量簡單圖的同構(gòu)來說的不變量 invariants（不變量）（不變量） - things that G1 and G2 must have in common to be isomorphic.282022-3-205.3 Representing Graphs and Graph Isomorphism Important invariants in isomorphic graphs:同構(gòu)圖中

23、的重要同構(gòu)圖中的重要不變量不變量n 相同的頂點數(shù)相同的頂點數(shù)n 有相同的邊數(shù)有相同的邊數(shù)n 有相同的頂點度有相同的頂點度n if one is bipartite, the other must ben if one is complete, the other must ben if one is a wheel, the other must beetc. 292022-3-205.3 Representing Graphs and Graph Isomorphism Example 5 Are the following two graphs isomorphic?Solution: T

24、hey are isomorphic, because they can be arranged to look identical. You can see this if in the right graph you move vertex b to the left of the edge a, c. Then the isomorphism f from the left to the right graph is: f(a) = e, f(b) = a, f(c) = b, f(d) = c, f(e) = d. 302022-3-205.3 Representing Graphs

25、and Graph Isomorphism Example 6 Show that the following two graphs are isomorphic.Proof: n Check invariantsn Try to find an isomorphism fn Show that f preserves adjacency relationv1v5v2v4v3u1u5u4u3u2312022-3-205.3 Representing Graphs and Graph Isomorphism Example 7 Determine whether the given pair o

26、f graphs is isomorphic?(1) (2) (3) 322022-3-20 5.3 Representing Graphs and Graph Isomorphism Homework: P. 467 8, 15, 17, 34-37 33 道路和回路道路和回路 圖圖G=(V,E)的一個頂點與邊相交替的序列的一個頂點與邊相交替的序列=v0e1v1vk-1ekvk，且邊，且邊ei的端的端點為點為vi-1和和vi (i=1,2,k)，則稱，則稱為一條為一條道路道路(路徑路徑path)，又稱為，又稱為v0vk道道路路。v1v2v3v4v6v5v7v8e1e2e3e4e5e6e7e8

27、e9e10e11e12=v1 e2 v3 e5 v4是一條道路若圖若圖G中的中的所有邊均不相同所有邊均不相同簡單道路；簡單道路；若道路若道路中中v0=vk(即首尾相同即首尾相同)回路；回路；若回路若回路中沒有重復邊中沒有重復邊簡單回路。簡單回路。v1v2v3v4v6v5v7v8e1e2e3e4e5e6e7e8e9e10e11e12C= v5 e8 v7 e12 v8 e10 v6 e7 v5是一回路 頂點頂點v1v7代表七座城市，有方向的邊代表七座城市，有方向的邊vivj表示從表示從vi城到城到vj城的單行車道，問從城的單行車道，問從v1城到城到v7城有無道路相城有無道路相通？通？ 如下圖所示

28、：如下圖所示：v1v2v3v4v5v6v7通過觀察上圖容易得出解答。通過觀察上圖容易得出解答。 如果我們進一步問：若如果我們進一步問：若v1城到城到v7有道有道路相通，共有幾條不同的道路？路相通，共有幾條不同的道路？v1v2v3v4v5v6v7A0 1 0 0 1 0 00 0 0 0 0 0 00 1 0 0 0 1 11 0 1 0 1 0 11 0 0 1 0 1 00 0 1 0 0 0 00 0 0 0 0 1 0 1 2 3 4 5 6 71234567考察鄰接矩陣：考察鄰接矩陣： AA1 0 0 1 0 1 00 0 0 0 0 0 00 0 1 0 0 1 01 2 0 1 1

29、 3 11 1 2 0 2 0 10 1 0 0 0 1 10 0 1 0 0 0 02A)()2(ija0 1 0 0 1 0 00 0 0 0 0 0 00 1 0 0 0 1 11 0 1 0 1 0 11 0 0 1 0 1 00 0 1 0 0 0 00 0 0 0 0 1 00 1 0 0 1 0 00 0 0 0 0 0 00 1 0 0 0 1 11 0 1 0 1 0 11 0 0 1 0 1 00 0 1 0 0 0 00 0 0 0 0 1 0001000011100001一般有：kA77)()(kija)3(ija71)2(kkjikaa71)2(kkjikaa其中：

30、A1 1 2 0 2 0 10 0 0 0 0 0 00 1 1 0 0 1 12 1 4 1 2 2 12 3 0 2 1 5 20 0 1 0 0 1 00 1 0 0 0 1 12A3A)()3(ija)(kija其中：71)1(hhjkihaa現(xiàn)在來看看現(xiàn)在來看看 的值有什么實際意義。以的值有什么實際意義。以 為例：為例：)2(ija71kkjikaajiaa11jiaa22 jiaa77)(kija)2(ija當且僅當0ljilaa1ljilaa表示從 出發(fā)兩步到達 的路徑數(shù)目ivjv同理ivjv表示從 出發(fā)k步到達 的路徑數(shù)目)(kija若要追問這一路徑是什么？途經(jīng)哪幾個點？只要回

31、溯 是如何形成即可求得)(kija例如例如 ，我們來看一下它的形成過程：，我們來看一下它的形成過程：)3(17a （1 1 2 0 2 0 1）0 1 0 0 1 0 00 0 0 0 0 0 00 1 0 0 0 1 11 0 1 0 1 0 11 0 0 1 0 1 00 0 1 0 0 0 00 0 0 0 0 1 0)3(1A)2(1A（1 0 0 1 0 1 0）0 1 0 0 1 0 00 0 0 0 0 0 00 1 0 0 0 1 11 0 1 0 1 0 11 0 0 1 0 1 00 0 1 0 0 0 00 0 0 0 0 1 0（0 1 0 0 1 0 0）（1 0 0

32、 1 0 1 0）)1(1A （0 1 0 0 1 0 0）)2(1A)1(1AAA154154715415155447432022-3-205.4 Connectivity 【 Theorem 】設設G是帶有相對于頂點順序是帶有相對于頂點順序v1, v2, . . . vn的鄰接的鄰接矩陣矩陣A的圖（允許帶有向邊或無向邊，帶多重邊和環(huán)）。的圖（允許帶有向邊或無向邊，帶多重邊和環(huán)）。從從 vi到到vj的長度為的長度為r的不同通路的數(shù)目等于的不同通路的數(shù)目等于Ar的第（的第（i,j)項，其項，其中中r是正整數(shù)。是正整數(shù)。 Note: This is the standard power of A

33、, not the Boolean product.Proof: LetnnijaA)(A ) 1 (01ijijaa2 )2(AnkkjikijnnijaabbAAA12,)(EVVEVVaaaajkkikjikkjik),( ,),(11bij: the number of different paths of length 2 from vi to vj nnijrcA)(nnijrrdAAA)(1nkkjiknjinjijiijacacacacd12211442022-3-205.4 ConnectivityExample 1(1)How many paths of length 2

34、are there from v5 to v4? a54 in A2; 1 (2) The number of paths not exceeding 6 are there from v4 to v5? a45 in A+A2+A3+A4+A5+A6 ; 2 (3) The number of circuits starting at vertex v5 whose length is not exceeding 6? 對圖對圖G=(V,E) 而言，若兩頂點而言，若兩頂點vi,vj 間存在路徑，則稱間存在路徑，則稱vi,vj 相連通；相連通； 無向圖無向圖G中中,若任意兩點都連通，則稱若任意

35、兩點都連通，則稱G為連通圖為連通圖(connected graph) ，否則為非連通圖；，否則為非連通圖；非連通圖可分解為若干個連通子圖非連通圖可分解為若干個連通子圖(連通分量連通分量);每個連通分量均有極大連通子圖。每個連通分量均有極大連通子圖。連通圖非連通圖462022-3-205.4 Connectivity 若無向圖每一對不同的頂點之間都有通路，則該圖稱為連通的若無向圖每一對不同的頂點之間都有通路，則該圖稱為連通的. Example 2 Are the following graphs connected?Yes.No.472022-3-205.4 Connectivity 【 The

36、orem 】 在連通無向圖的每一對不同頂點之間都存在在連通無向圖的每一對不同頂點之間都存在簡單通路簡單通路Proof:Because the graph is connected there is a path between u and v. Throw out all redundant circuits to make the path simple.因為圖是連通的，是喲以因為圖是連通的，是喲以u和和v之間至少有之間至少有1條通路。刪除所有冗余的回路使得通路更短。條通路。刪除所有冗余的回路使得通路更短。連通分支For example,482022-3-205.4 Connectivity

37、 有時刪除一個頂點和它所關聯(lián)的邊，就產(chǎn)生帶有比原圖更多的連通分支有時刪除一個頂點和它所關聯(lián)的邊，就產(chǎn)生帶有比原圖更多的連通分支的子圖。把這樣的頂點稱為的子圖。把這樣的頂點稱為割點（或節(jié)點）割點（或節(jié)點）。從連通圖里刪除割點，就。從連通圖里刪除割點，就產(chǎn)生不連通的子圖。產(chǎn)生不連通的子圖。同理，把一旦刪除就產(chǎn)生帶有比原圖更多的連通分支的子圖的邊稱為同理，把一旦刪除就產(chǎn)生帶有比原圖更多的連通分支的子圖的邊稱為割割邊或橋邊或橋For example,（1）In the star network the center vertex is a cut vertex. All edges are cut edges.在星