圖的基本概念-全文預(yù)覽
【正文】 ＝ 2， K7＝ λ 7＝ 0， K8＝ λ 8＝ 0。 圖 λ ＝ 1， 它只能是 1邊 連通圖。 若 λ( G)≥ r， 則稱 G是 r 邊 連通圖 。 K5的點(diǎn)連通度 K＝ 4， 所以 K5是 1連通圖， 2連通圖， 3連通圖， 4連通圖。 說(shuō)明 連通度是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目。 無(wú)向圖的邊割集 定義 設(shè)無(wú)向圖 G＝ V,E， 若存在 E ??E， 且 E ?≠ ?， 使得 p(GE ?)p(G)， 而對(duì)于任意的 E ???E?， 均有 p(GE ??)＝p(G)， 則稱 E?是 G的 邊割集 ，或簡(jiǎn)稱為 割集 。 如何定義連通度 ?問(wèn)題 ：如何定量地比較無(wú)向圖的連通性的強(qiáng)與弱？ ?點(diǎn)連通度 ：為了破壞連通性，至少需要?jiǎng)h除多少個(gè)頂點(diǎn)？ ?邊連通度 ：為了破壞連通性，至少需要?jiǎng)h除多少條邊？ ?“ 破壞連通性 ” 是指 “ 變得更加不連通 ” 。 距離有以下性質(zhì)： (1)d(u,v)≥0 ， u＝ v時(shí)，等號(hào)成立。 若 G為非連通圖，則 p(G)≥2 。 連通圖與連通分支 若無(wú)向圖 G是平凡圖或 G中任何兩個(gè)頂點(diǎn)都是連通的，則稱 G為 連通圖 ，否則稱 G是 非連通圖 或 分離圖 。 (4)在非簡(jiǎn)單標(biāo)定圖中，當(dāng)只用頂點(diǎn)序列表示不出某些通路 (回路 )時(shí)，可在頂點(diǎn)序列中加入一些邊 (這些邊是平行邊或環(huán) )，可稱這種表示法為 混合表示法 。定義 Г 可以表示成 ej1 ,ej2 ,… ,ejl。 ?若 Г 中有 邊重復(fù) 出現(xiàn)，則稱 Г 為 復(fù)雜通路 ， 又若 vi0＝ vil， 則稱 Г 為 復(fù)雜回路 。 若 Г的 所有邊各異 ， 則稱 Г為 簡(jiǎn)單通路 ， 又若 vi0＝ vil， 則稱 Г為 簡(jiǎn)單回路 。 (4)設(shè) u,v∈ V(u,v可能相鄰，也可能不相鄰 )， 用 G∪( u,v)(或G+(u,v))表示在 u,v之間加一條邊 (u,v)， 稱為 加新邊 。 設(shè) E ??E， 用 GE ?表示從 G中刪除 E ?中所有的邊，稱為 刪除 E ?。 定義 定義 設(shè) G＝ V,E為 n階無(wú)向簡(jiǎn)單圖， 以 V為頂點(diǎn)集 ，以所有 使 G成為完全圖 Kn的添加邊組成的集合 為邊集的圖，稱為 G的 補(bǔ)圖 ，記作 G。 設(shè) G＝ V,E為一圖， V1?V且 V1≠ ?， 稱以 V1為頂點(diǎn)集，以G中 兩個(gè)端點(diǎn)都在 V1中的邊 組成邊集 E1的圖為 G的 V1導(dǎo)出的子圖 ，記作 G[V1]。 當(dāng) k為奇數(shù)時(shí)， n必為偶數(shù)。 設(shè) D為 n階有向簡(jiǎn)單圖，若 D中每個(gè)頂點(diǎn)都鄰接到其余的 n1個(gè)頂點(diǎn)，又鄰接于其余的 n1個(gè)頂點(diǎn)，則稱 D是 n階有向完全圖 。 ??n1iid可圖化，不可簡(jiǎn)單圖化。 例 (3) (3,3,3,1) 可圖化，不可簡(jiǎn)單圖化。 證明 因?yàn)?G既無(wú)平行邊也無(wú)環(huán)， 所以 G中任何頂點(diǎn) v至多與其余的 n1個(gè)頂點(diǎn)均相鄰， 于是 d(v)≤ n1， 由于 v的任意性，所以△ (G)≤ n1。 由已知條件可知， d中有偶數(shù)個(gè)奇數(shù)度點(diǎn)。 度數(shù)列舉例 按頂點(diǎn)的標(biāo)定順序，度數(shù)列為 4,4,2,1,3。 對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。 說(shuō)明： (1)很多離散問(wèn)題可以用圖模型求解。 證明 設(shè) G＝ V， E為任意一圖，令 V1＝ {v|v∈V∧ d(v)為奇數(shù) } V2＝ {v|v∈V∧ d(v)為偶數(shù) } 則 V1∪V 2＝ V， V1∩V 2＝ ? ， 由握手定理可知 ???Vvvdm )(2 ??????21)()(VvVvvdvd由于 2m和 ?? 2)(Vvvd，所以 ?? 1)(Vvvd為偶數(shù) ， 但因 V1中頂點(diǎn)度數(shù)為奇數(shù)， 所以 |V1|必為偶數(shù)。 d+(a)＝ 4， d(a)＝ 1 (環(huán) e1提供出度 1，提供入度 1)， d(a)＝ 4+1＝ 5。 稱 d+(v)+d(v)為 v的 度數(shù) ，記做 d(v)。 頂點(diǎn)的度數(shù) 定義 設(shè) G＝ V,E為一無(wú)向圖， ?v∈V ， 稱 v作為邊的端點(diǎn)次數(shù)之和為 v的度數(shù) ，簡(jiǎn)稱為 度 ，記做 dG(v)。 含平行邊的圖稱為 多重圖 。 稱 Г +D(v)∪Г D(v)為 v的 鄰域 ，記做 ND(v)。 稱 NG(v)∪{ v}為 v的 閉鄰域 ，記做 NG(v)。 ?設(shè)有向圖 D＝ V， E， vi， vj∈V ， ek， el∈E 。 ?無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)的頂點(diǎn)均稱為 孤立點(diǎn) 。 若 vi＝ vj， 則稱 ek與 vi的 關(guān)聯(lián)次數(shù)為 2，并稱 ek為 環(huán) 。 ?將有向圖各 有向邊均改成無(wú)向邊后的無(wú)向圖 稱為原來(lái)圖的 基圖 。 ?若 |V(G)|與 |E(G)|均為有限數(shù)，則稱 G為 有限圖 。 圖的一些概念和規(guī)定 ?G表示無(wú)向圖，但有時(shí)用 G泛指圖 (無(wú)向的或有向的 )。 （ 2） E為 邊集 ，它是 笛卡兒積 V V的多重子集，其元素稱為 有向邊 ，簡(jiǎn)稱 邊 。 定義 一個(gè) 無(wú)向圖 是一個(gè)有序的二元組 V， E,記作 G， 其中 （ 1） V≠ ?稱為 頂點(diǎn)集 ，其元素稱為 頂點(diǎn) 或 結(jié)點(diǎn) 。 例如 在多重集合 {a,a,b,b,b,c,d}中， a,b,c,d的重復(fù)度分別為 2,3,1,1。 定義 一個(gè) 有向圖 是一個(gè)有序的二元組 V， E， 記作 D， 其中 （ 1） V≠ ?稱為 頂點(diǎn)集 ，其元素稱為 頂點(diǎn) 或 結(jié)點(diǎn) 。 畫(huà)出 G與 D的圖形。 ?若 |V(G)|＝ n， 則稱 G為 n階圖 。 標(biāo)定圖與非標(biāo)定圖、基圖 ?將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用 ek表示 無(wú)向邊(vi,vj)（ 或 有向邊 vi,vj）， 并稱 頂點(diǎn)或邊用字母標(biāo)定的圖 為 標(biāo)定圖 ，否則稱為 非標(biāo)定圖 。 若 vi≠ vj， 則稱 ek與 vi或 ek與 vj的 關(guān)聯(lián)次數(shù)為 1。 若
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1