【正文】 vi 可達(dá) vj 否則 (3). 求可達(dá)矩陣 可達(dá)矩陣的求法 ：由鄰接矩陣 A計(jì)算 A2,A+A2,…… A+A2+…+ A(r) = B = (bij(r))n?n pij = 1 bij(r) ? 0 0 bij(r) = 0 則 i ? j pii = 1 即得可達(dá)矩陣 P(D) = (pij)nxn 說明 : 求通路 r|v| 。 vi 關(guān)聯(lián) ej（ 環(huán) ?2） vi 不關(guān)聯(lián) ej 一、關(guān)聯(lián)矩陣及其性質(zhì) 圖的矩陣表示 v4 e1 e2 e3 e4 e5 v1 v2 v3 強(qiáng)調(diào)： 頂點(diǎn)與邊的關(guān)系 ， (mij)n m行 n為 ？ m為 ？ 無向圖的關(guān)聯(lián)矩陣的性質(zhì) ： ))(,2,1(2)1(n1iij 每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)mjm ?????))(()2( iim1jij 的度數(shù)vvdm ?????????n1iiij )(2)3( vdmm是孤立點(diǎn)當(dāng)且僅當(dāng)???m1jiij 0)4( vm為平行邊與列相同，說明列與第若第 kj)5( eekj(?定理 ) v4 e1 e2 e3 e4 e5 v1 v2 v3 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0 (?圖與矩陣 ) (2) 設(shè) D = V,E 是有向圖且 無環(huán) ，令： mij = 1 0 則稱 M(D) = (mij)n m為 D的 關(guān)聯(lián)矩陣 。是 G的點(diǎn)割集 。 (必要性 ) D是強(qiáng)連通的，則 D中任何兩個(gè)頂點(diǎn)都是可達(dá)的 。 四、有向圖的連通性 ： (1) 如果有向圖 D = V,E 中 所有有向邊的方向去掉后所得圖為 無向連通圖 ，則說 D為 弱連通圖 。 三、無向圖的連通性 連通分支 ：無向圖 G中每個(gè)劃分塊稱為 G的一個(gè)連通分支 ， p(G)表示連通分支的個(gè)數(shù) 。（簡單通 路 ？ ） (3) 在 n階圖中，如果存在從 vi到自身的回路，則從 vi 到自身存在 長度小于等于 n的回路 。 在 上述通 路中， 去掉 vs到 vs的這些邊，至少去掉一條邊后仍是 vi到 vj的一條通路。 例 就下圖中 V1到 V3初級通路多少條 ?簡單通路 ?通路 ?， V1到 V1長度為 6的初級回路 ?簡單回路 ?回路 ?。 (回路中必須有邊 ？ ） 一、通路與回路的概念 通路、回路、圖的連通性 簡單通路 ： ? = v0 e1 v1 e2… ek vk為通路且 邊 e1 e2… ek 互不相同 ，又稱之為 跡 ，可簡用 v0 v1 … vk 來表示。 （ 4） 思考： 3頂點(diǎn) 3邊的所有可能非同構(gòu)的有向簡單圖？ 例 3個(gè)頂點(diǎn) 2條邊的所有可能非同構(gòu)的有向簡單圖 。的重?cái)?shù)相同 則說 G ? G39。 ， 如果存在 g:V?V39。 如：圖 為 的子圖， 則圖 (1) (2) (3) 為 (1)相對于 (2)的補(bǔ)圖。 則 G39。39。 ，滿足 (1) E39。 = V39。 v1 v4 v3 v2 e1 e2 e3 e4 e5 e8 e6 e7 v5 思考 : V={ v1,v2}頂點(diǎn)集 的 導(dǎo)出子圖 ? E={e1,e3}為邊集 的 導(dǎo)出子圖 ? 例 列舉下圖的一些子圖、真子圖、生成子圖、導(dǎo)出子圖。 ?G。?V， E39。？ 3） 完全圖是簡單圖 ？ 1階有向完全圖？ 四、子圖與母圖 (1) G = V, E ， G39。 mvdvdniinii ?? ??????11)()(例 (3,3,2,3)， (1,3,3,3)能成為 無向 圖的度數(shù)序列嗎？能成為 無向簡單 圖的度數(shù)序列嗎？ (5,4,3,2,2) (4,4,3,3,2,2)? 例 有向簡單 圖的度數(shù)序列 (3,3,3,3)，它的入度能為 (1,1,1,1)嗎？ 例 已知圖 G中有 10條邊， 4個(gè) 3度頂點(diǎn)， 其余頂點(diǎn)的度數(shù)均小于等于 2，問 G 中至少有多少個(gè)頂點(diǎn)？ 正則圖 ： 各頂點(diǎn)的度都相同的圖為正則圖； 各頂點(diǎn)的度均為 k的圖為 k次 正則圖。 ???Vv||2)( Evd即握手定理的推論 ： 任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)一定為偶數(shù)。 例： 判斷多重圖與簡單圖？ v1 v4 v3 v2 e1 e2 e3 e4 e5 e8 e6 e7 v5 e1 e2 e3 e4 e5 v1 v2 v3 v5 v4 e1 e3 e2 e4 v1 v2 v3 v5 v4 度 ： (1) 在無向圖 G = V, E 中，與頂點(diǎn) v(v?V)關(guān)聯(lián)的邊的數(shù)目 (每個(gè)環(huán)計(jì)算兩次 )， 記作： d(v)。 平行邊 ： 無向圖中，關(guān)聯(lián)一對結(jié)點(diǎn)的無向邊多于一條，平行邊的條數(shù)為 重?cái)?shù) ； 多重圖 ： ?包含平行邊的圖。 2. 有向圖 v1 v4 v3 v2 e1 e2 e3 e4 e5 e6 (a) v1 v4 v3 v2 e1 e2 e3 e4 e5 e6 (b) 如 (a)： D=V, E， V={v1,v2,v3,v4}， E={v2,v1,v2,v2,v3,v2,v3,v4,v4,v3,v4,v4} 如 (b)： D=V, E， V={v1,v2,v3 ,v4}， E={v1,v3,v2,v2,v3,v4,v4,v3,v4,v1,v4,v1} 思考 ： 與以前講到的什么相似？ 有限圖 ： V， E均為有窮集合 零 圖 ： E ? ? 平凡圖 ： E ? ? 且 |V| = 1 (n, m)圖 ： |V| = n 且 |E| = m 頂點(diǎn)與邊關(guān)聯(lián) ： 如果 ek = (vi,vj) ?E， 稱 ek與 vi關(guān)聯(lián) ，或 ek與 vj關(guān)聯(lián) 。 習(xí)慣上，無序?qū)?{a,b}改記成 (a, b) 有序?qū)?(a,b)均用 a,b 無序積 ： 設(shè) A， B為二集合， =(b,a) ≠b,a 1. 無向圖 無向圖 ： 無向圖 G是一個(gè)二元組 V,E ， 其中 (1) V是一個(gè)非空集 ––– 頂點(diǎn)集 V(G)， 每個(gè)元素為 頂點(diǎn)或結(jié)點(diǎn) ； (2) E是無序積 V amp。 a d c b 我們 不關(guān)心邊的長短與形狀 。 計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué) ， 信息論 ， 控制論 ， 網(wǎng)絡(luò)理論 ， 化學(xué)生物學(xué) ， 物理學(xué) 。第 8講 圖的基本概念 重點(diǎn) ?重要概念：簡單圖， 度與握手定理、完全圖、同構(gòu)圖 ?通路、回路、圖的連通性 ?圖的矩陣表示與應(yīng)用 ?歐拉圖與哈密爾頓圖 難點(diǎn) 同構(gòu)圖，割集，初級通路與簡單通路區(qū)別 18世紀(jì)： 哥尼斯堡 (Konigsiberg)七橋問題 圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門新興學(xué)科。 在計(jì)算機(jī)學(xué)科中，計(jì)算機(jī)網(wǎng)絡(luò)、操作系統(tǒng) 數(shù)據(jù)庫，數(shù)據(jù)結(jié)構(gòu)等等都與圖論 有重要的聯(lián)系。 一、基本圖類及相關(guān)概念 無向圖及有向圖 如右圖，這是不同于幾何圖形的另一數(shù)學(xué)結(jié)構(gòu)。B。 如 (1)： G=V, E， V={v1,v2,v3,v4}，