圖表示和圖同構(gòu)課件

1、圖表示和圖同構(gòu)圖表示和圖同構(gòu)內(nèi)容提要圖的表示 鄰接矩陣的運(yùn)算圖的同構(gòu) 內(nèi)容提要圖的表示 圖的表示 關(guān)聯(lián)矩陣鄰接矩陣鄰接表 圖的表示 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣(incidence matrix) 無向圖G = (V, E, ) ，不妨設(shè)Vv1，vn，Ee1，em。M(G) mij稱為G的關(guān)聯(lián)矩陣(nm 階矩陣), 其中 無向圖G可以是偽圖（含自環(huán)或多重邊）。 vi(ej)關(guān)聯(lián)矩陣(incidence matrix) 無向圖G = 舉例（關(guān)聯(lián)矩陣）v1v2v3v4e1e2e3e4e5關(guān)聯(lián)矩陣表示法不適合于有向圖舉例（關(guān)聯(lián)矩陣）v1v2v3v4e1e2e3e4e5關(guān)聯(lián)矩陣鄰接矩陣(adjacency mat

2、rix)簡單有向圖G = (V, E, ) ，設(shè)Vv1，vn，Ee1，em。A(G)aij稱為G的鄰接矩陣(nn 階矩陣)，其中 eE. (e)=(vi, vj)鄰接矩陣(adjacency matrix)簡單有向圖G =舉例（鄰接矩陣）v1v2v3v4可推廣到簡單無向圖舉例（鄰接矩陣）v1v2v3v4可推廣到簡單無向圖舉例（鄰接矩陣）v1v2v3v4簡單無向圖的鄰接矩陣是對(duì)稱矩陣舉例（鄰接矩陣）v1v2v3v4簡單無向圖的鄰接矩陣是對(duì)稱矩鄰接表若圖G = (V, E, ) 沒有多重邊，列出這個(gè)圖的所有邊。對(duì)每個(gè)頂點(diǎn)，列出與其鄰接的頂點(diǎn)。是單射頂 點(diǎn)相鄰頂點(diǎn)ab, c, ebaca, d, e

3、dc, eea, c, dacbed鄰接表若圖G = (V, E, ) 沒有多重邊，列出這個(gè)圖鄰接表（有向圖）若圖G = (V, E, ) 沒有多重邊，列出這個(gè)圖的所有邊。對(duì)每個(gè)頂點(diǎn)，列出與其鄰接的頂點(diǎn)。是單射頂 點(diǎn)相鄰頂點(diǎn)ab, c, d, ebb, dca, c, edeb, c, dacbed鄰接表（有向圖）若圖G = (V, E, ) 沒有多重邊，關(guān)于鄰接矩陣通常，鄰接矩陣中的元素為0和1，稱為布爾矩陣。鄰接矩陣也可表示包含多重邊的圖，此時(shí)的矩陣不是布爾矩陣。v1v2v3v4關(guān)于鄰接矩陣通常，鄰接矩陣中的元素為0和1，稱為布爾矩陣。v關(guān)于鄰接矩陣當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就

4、是關(guān)系矩陣。無向圖的鄰接矩陣是對(duì)稱的。圖G的鄰接矩陣中的元素的次序是無關(guān)緊要的，行與行、列與列進(jìn)行相應(yīng)交換，則可得到相同的矩陣。若有二個(gè)簡單有向圖，則可得到二個(gè)對(duì)應(yīng)的鄰接矩陣，若對(duì)某一矩陣行與行、列與列之間的相應(yīng)交換后得到和另一矩陣相同的矩陣，則此二圖同構(gòu)。關(guān)于鄰接矩陣當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就是關(guān)系矩鄰接矩陣的運(yùn)算頂點(diǎn)的度行中1的個(gè)數(shù)就是行中相應(yīng)結(jié)點(diǎn)的出度列中1的個(gè)數(shù)就是列中相應(yīng)結(jié)點(diǎn)的入度Deg+(1)=1,Deg-(1)=2 Deg+(2)=2,Deg-(2)=2 Deg+(3)=3,Deg-(3)=1 Deg+(4)=1,Deg-(4)=2v1v2v3v4鄰接矩陣的運(yùn)算頂點(diǎn)

5、的度Deg+(1)=1,Deg-(1)=2鄰接矩陣的運(yùn)算逆圖（轉(zhuǎn)置矩陣）設(shè)的鄰接矩陣為A，則G的逆圖的鄰接矩陣是A的轉(zhuǎn)置矩陣，用AT表示。鄰接矩陣的運(yùn)算逆圖（轉(zhuǎn)置矩陣） bij表示結(jié)點(diǎn)i和結(jié)點(diǎn)j均有邊指向的那些結(jié)點(diǎn)的個(gè)數(shù)； 若ij，則bii表示結(jié)點(diǎn)i的出度。鄰接矩陣的運(yùn)算 bij表示結(jié)點(diǎn)i和結(jié)點(diǎn)j均有邊指向的那些結(jié)點(diǎn)的個(gè)數(shù)；鄰接矩 Cij表示同時(shí)有邊指向結(jié)點(diǎn)i和結(jié)點(diǎn)j的那些結(jié)點(diǎn)的個(gè)數(shù)； 若ij，則Cii表示結(jié)點(diǎn)i的入度。鄰接矩陣的運(yùn)算 Cij表示同時(shí)有邊指向結(jié)點(diǎn)i和結(jié)點(diǎn)j的那些結(jié)點(diǎn)的個(gè)數(shù)；鄰接v1v2v3v4鄰接矩陣的運(yùn)算v1v2v3v4鄰接矩陣的運(yùn)算 若aikakj1，則表示有ikj長度為2

6、的有向邊； dij表示i和j之間具有長度為2的通路個(gè)數(shù)。鄰接矩陣的運(yùn)算 若aikakj1，則表示有ikj長度為2的有向邊；鄰接矩陣的運(yùn)算v1v2v3v4 從v2v1，有二條長度為2的通路；有一條長度為3的通路鄰接矩陣的運(yùn)算v1v2v3v4 從v2v1，有二條長度為2長度不大于k的通路個(gè)數(shù)鄰接矩陣的運(yùn)算v1v2v3v4長度不大于k的通路個(gè)數(shù)鄰接矩陣的運(yùn)算v1v2v3v4圖的同構(gòu)圖同構(gòu)的定義設(shè)G1=(V1, E1, 1)和G2=(V2, E2, 2)是兩個(gè)簡單無向圖。若存在雙射f: V1V2, u和v在G1中相鄰當(dāng)且僅當(dāng) f(u)和f(v)在G2中相鄰。此時(shí)稱f是一個(gè)同構(gòu)函數(shù)。設(shè)G1=(V1, E

7、1, 1)和G2=(V2, E2, 2)是兩個(gè)無向圖。若存在雙射f: V1V2, g: E1E2, eE1, 1(e)=u, v, 當(dāng)且僅當(dāng) g(e)E2, 且2(g(e)=f(u), f(v)。 圖的同構(gòu)圖同構(gòu)的定義圖同構(gòu)的例子圖同構(gòu)的例子圖同構(gòu)的例子圖同構(gòu)的例子檢測兩個(gè)簡單圖是否同構(gòu)鄰接矩陣表示：n！個(gè)現(xiàn)有最好算法在最壞情況下的時(shí)間復(fù)雜性是指數(shù)級(jí)。（在最壞情況下）時(shí)間復(fù)雜性為多項(xiàng)式的算法？檢測兩個(gè)簡單圖是否同構(gòu)鄰接矩陣表示：n！個(gè)檢測兩個(gè)簡單圖是否同構(gòu)圖同構(gòu)下保持的性質(zhì)稱為圖不變的頂點(diǎn)數(shù)、度序列、利用圖不變的性質(zhì)（沒有保持）來推斷出不同構(gòu)acbedacbed圖G圖H檢測兩個(gè)簡單圖是否同構(gòu)圖同構(gòu)下保持的性質(zhì)稱為圖不變的acbe檢測兩個(gè)簡單圖是否同構(gòu)acbdehfgsutvwzxyu1