離散數(shù)學(xué)圖的概念與表-文庫吧
2025-01-01 20:15 本頁面
【正文】 在圖的定義中 ， 強調(diào)的是結(jié)點集 、 邊集以及邊與結(jié)點的關(guān)聯(lián)關(guān)系 ， 既沒有涉及到聯(lián)結(jié)兩個結(jié)點的邊的長度 、 形狀和位置 ， 也沒有給出結(jié)點的位置或者規(guī)定任何次序 。 因此 ， 對于給定的兩個圖 ， 在它們的圖形表示中 ， 即在用小圓圈表示結(jié)點和用直線或曲線表示聯(lián)結(jié)兩個結(jié)點的邊的圖解中 ， 看起來很不一樣 ， 但實際上卻是表示同一個圖 。 因而 ， 引入兩圖的同構(gòu)概念便是十分必要的了 。 定義 給定無向圖 (或有向圖 )G1=V1， E1和 G2=V2， E2。 若存在雙射 f∈ V2V1， 使得對任意 v，u∈ V1， 有 〔 u， v〕 ∈ E1?〔 f(u)， f(v)〕 ∈ E2(或 u，v∈ E1f(u)， f(v)∈ E2)則稱 G1同構(gòu)于 G2， 記為 G1?G2。 顯然 ， 兩圖的同構(gòu)是相互的 ， 即 G1同構(gòu)于 G2， G2同構(gòu)于 G1。 由同構(gòu)的定義可知 ， 不僅結(jié)點之間要具有一一對應(yīng)關(guān)系 ， 而且要求這種對應(yīng)關(guān)系保持結(jié)點間的鄰接關(guān)系 。對于有向圖的同構(gòu)還要求保持邊的方向 。 一般說來 ， 證明兩個圖是同構(gòu)的并非是輕而易舉的事情 ， 往往需要花些氣力 。請讀者證明圖 。 根據(jù)圖的同構(gòu)定義，可以給出圖同構(gòu)的必要條件如下： (1) 結(jié)點數(shù)目相等； (2) 邊數(shù)相等； (3) 度數(shù)相同的結(jié)點數(shù)目相等。 但這僅僅是必要條件而不是充分條件。 滿足上述三個條件，然而并不同構(gòu)。因此在 (a)中度數(shù)為 3的結(jié)點 x與兩個度數(shù)為 1的結(jié)點鄰接，而 (b)中度數(shù)為 3的結(jié)點 y僅與一個度數(shù)為 1的結(jié)點鄰接。 尋找一種簡單有效的方法來判定圖的同構(gòu)，至今仍是圖論中懸而未決的重要課題。 例如圖 (a)與 (b) 圖 返回 返回 圖 鏈 (或路 )與圈 (或回路 ) 在無向圖 (或有向圖 )的研究中 ， 常常考慮從一個結(jié)點出發(fā) ， 沿著一些邊 (或弧 )連續(xù)移動而達到另一個指定結(jié)點 ， 這種依次由結(jié)點和邊 (或弧 )組成的序列 ， 便形成了鏈 (或路 )的概念 。 定義 給定無向圖 (或有向圖 )G=V， E。令v0， v1， … ， vm∈ V，邊 (或弧 )e1， e2， … ， em∈ E，其中vi1， vi是 ei的結(jié)點，交替序列 v0e1v1e2v2… emvm稱為連接 v0到 vm的鏈 (或路 )。 v0和 vm分別稱為鏈 (或路 )的始結(jié)點和終結(jié)點，而邊 (或弧 )的數(shù)目稱為鏈 (或路 )的長度。若 v0=vm時，該鏈 (或路 )稱為圈 (或回路 )。 定義 在一條鏈 (或路 )中，若出現(xiàn)的邊 (或弧 )都是不相同的，稱該鏈 (或路 )為簡單鏈(或簡單路 )；若出現(xiàn)的結(jié)點都是不相同的，稱該鏈 (或路 )為基本鏈 (或基本路 )。 顯然，每條基本鏈 (或基本路 )必定是簡單鏈 (或簡單路 )。 定義 在一圈 (或回路 )中，若出現(xiàn)的每條邊(或弧 )恰好一次，稱該圈 (或回路 )為簡單圈 (或簡單回路 )；若出現(xiàn)的每個結(jié)點恰好一次，稱該圈 (或回路 )為基本圈(或基本回路 )。 可以看出，對于簡單圖來說，鏈 (或路 )和圈 (或回路 )能夠僅用結(jié)點序列表示之。 定理 在一個圖中 ， 若從結(jié)點 vi到結(jié)點 vj存在一條鏈 (或路 )， 則必有一條從 vi到 vj的基本鏈 (或基本路 )。 定理 在一個具有 n個結(jié)點的圖中 ， 則 (1) 任何基本鏈 (或路 )的長度均不大于 n1。 (2) 任何基本圈 (或路 )的長度均不大于 n。 定義 在一個圖中 ， 若從 vi到 vj存在任何一條鏈 (或路 )， 則稱從 vi到 vj是可達的 ， 或簡稱 vi可達 vj。 為完全起見 ， 規(guī)定每個結(jié)點到其自身是可達的 。 對于無向圖 G來說 ， 不難證明結(jié)點間的可達性是結(jié)點集合上的等價關(guān)系 。 因此它將結(jié)點集合給出一個劃分 ， 并且劃分中的每個元素形成一個誘導(dǎo)子圖；兩結(jié)點之間是可達的當且僅當它們屬于同一個子圖 ， 稱這種子圖為圖 G的連通分圖 ， 圖 G的連通分圖的個數(shù) ， 記為ω(G)。 定義 若圖 G只有一個連通分圖，則稱 G是連通圖；否則，稱圖 G為非連通圖或分離圖。 在圖的研究中 ， 常常需要考慮刪去與增加結(jié)點 、結(jié)點集 、 邊和邊集 （ 或弧集 ） 的問題 。 所謂從圖G=V,E中刪去結(jié)點集 S， 是指作 VS以及從 E中刪去與S中的全部結(jié)點相聯(lián)結(jié)的邊而得到的子圖 ， 記作 GS；特別當 S=|v|時 ， 簡記為 Gv；所謂從圖 G=V,E中刪去邊集 （ 或弧集 ） T， 是指作 ET， 且 T中的全部邊所關(guān)聯(lián)的結(jié)點仍在 V中而得到的子圖 ， 記為 GT；特別當 T={e}時 ，簡記作 Ge。 所謂圖 G=V,E增加結(jié)點集 S，是指作V∪ T以及向 E中并入 S中、 S與 V中所成的邊而得到的圖，記作 G+S；特別當 S={v}時，簡記為G+v；圖 G=V,E增加邊集（或弧集） T是指作E∪ T所得到的圖，記作 G+T，這里 T中全部邊（或?。┑年P(guān)聯(lián)結(jié)點屬于 V。 定義 給定連通無向圖 G=V， E， S?V。若ω(GS)＞ ω(G)，但 ?T?S有 ?(GT)=?(G)，則
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1