【正文】 e1,e2,e3}) 例 2022/2/13 計(jì)算機(jī)學(xué)院 45/172 完全圖 1. 設(shè) G＝ V,E為一個(gè)具有 n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖 ， 如果 G中任一個(gè)結(jié)點(diǎn)都與其余 n1個(gè)結(jié)點(diǎn)相鄰接 ， 則稱 G為 無(wú)向完全圖 ， 簡(jiǎn)稱 G為 完全圖 ， 記為 Kn。 7) 圖 G＝ V， E ， S?V， 則 G(S)=(S， E′ )是一個(gè)以 S為結(jié)點(diǎn) ， 以 E′ ={uv|u,v?S,uv?E}為邊集的圖 ， 稱為 G的點(diǎn)誘導(dǎo)子圖 。 5) 設(shè) v是圖 G的一個(gè)結(jié)點(diǎn) ， 從 G中刪去結(jié)點(diǎn) v及其關(guān)聯(lián)的全部邊后得到的圖稱為 G的刪點(diǎn)子圖 ， 簡(jiǎn)記為 G－ v。 3) 若 V2=V1， 則稱 H是 G的生成子圖 。證明：（略）。由于上式中的 2m和 |V2|(偶數(shù)之和為偶數(shù) )均為偶數(shù)，因而也為偶數(shù)。 ■ d e g ( ) 2vVvm??? ；2022/2/13 計(jì)算機(jī)學(xué)院 31/172 推論 在圖 G＝ V， E中 ， 其 V＝ {v1,v2,v3,… ,vn}， E＝ {e1， e2， …… ， em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。 2) 在有向圖 G＝ V， E中 ， 以結(jié)點(diǎn) v為始點(diǎn)引出的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的出度 ,記為 deg+(v)；以結(jié)點(diǎn) v為終點(diǎn)引入的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的入度 ,記為 deg(v)；而結(jié)點(diǎn)的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點(diǎn)的度數(shù) ， 記為 deg(v)，即 deg(v)＝ deg+(v)+deg(v)； 2022/2/13 計(jì)算機(jī)學(xué)院 21/172 結(jié)點(diǎn)的度數(shù) 1) 在無(wú)向圖 G＝ V， E中 ， 與結(jié)點(diǎn) v(v?V)關(guān)聯(lián)的邊的條數(shù) （ 有環(huán)時(shí)計(jì)算兩次 ） ， 稱為該結(jié)點(diǎn)的度數(shù) ， 記為 deg(v)；最大點(diǎn)度和最小點(diǎn)度分別記為 ?和 ?。 2) 在無(wú)向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為平行邊； 3) 含有平行邊的圖稱為 多重圖 ； 4) 含有 環(huán) 的多重圖稱為 廣義圖 （ 偽圖 ） ； 5) 滿足定義 簡(jiǎn)單圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 12/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無(wú)序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為無(wú)向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè)端點(diǎn)； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的始點(diǎn) 。 2022/2/13 計(jì)算機(jī)學(xué)院 10/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無(wú)序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為無(wú)向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè)端點(diǎn) ； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為 有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的 始點(diǎn) 。 2022/2/13 計(jì)算機(jī)學(xué)院 7/172 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為結(jié)點(diǎn) ,簡(jiǎn)稱點(diǎn) ， V為結(jié)點(diǎn)集； 2） E（ G） ＝ {e1,e2,e3,… ,em}是一個(gè)有限的集合 ， ei(i＝ 1,2,3,… ,m)稱為 邊 ， E為 邊集 ， E中的每個(gè)元素都是由 V中不同結(jié)點(diǎn)所構(gòu)成的無(wú)序?qū)?， 且不含重復(fù)元素 。B ＝ {(a,b)|a∈A ， b∈B} 為 A 與 B 的 無(wú)序積 ， （ a,b ） 稱為 無(wú)序?qū)? 。 ?與序偶不同 ， 無(wú)論 a,b是否相等 ， 均有： (a,b)＝ (b,a)。 3） 圖 G的結(jié)點(diǎn)數(shù)稱為 G的階 ， 用 n表示 ， G的邊數(shù)用 m表示 ，也可表示成 ?(G)=m 。 v是邊 e的 終點(diǎn) ， 統(tǒng)稱為 e的 端點(diǎn) ； e是 u的出邊 ， 是 v的入邊 。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個(gè)簡(jiǎn)單圖 ， 稱為原來(lái)圖的基圖 。 2) 在 有向圖 G＝ V， E中 ， 以結(jié)點(diǎn) v為始點(diǎn)引出的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 出度 ,記為 deg+(v)；以結(jié)點(diǎn) v為終點(diǎn)引入的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 入度 ,記為 deg(v)；而結(jié)點(diǎn)的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點(diǎn)的 度數(shù) ， 記為 deg(v)，即 deg(v)＝ deg+(v)+deg(v)； 2022/2/13 計(jì)算機(jī)學(xué)院 22/172 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為 孤立結(jié)點(diǎn) ；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖； 只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為 平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn) 。 設(shè) V1＝ {v|v?V且 deg(v)＝奇數(shù) }， V2＝ {v|v?V且deg(v)＝偶數(shù) }。于是 |V1|為偶數(shù) (因?yàn)?V1中的結(jié)點(diǎn) v之 deg(v)都為奇數(shù) )，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。 2022/2/13 計(jì)算機(jī)學(xué)院 35/172 度數(shù)序列 ?設(shè) V ＝ {v1, v2,… ,vn} 為圖 G 的 結(jié) 點(diǎn) 集 ， 稱(deg(v1),deg(v2),… ,deg(vn))為 G的 度數(shù)序列 。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的平凡子圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 39/172 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 8) 圖 G＝ V， E ， T?E且 T≠ ?， 則 G（ T） 是一個(gè)以 T為邊集 ， 以 T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖 ，稱為 G的邊誘導(dǎo)子圖 。 2. 設(shè) G＝ V,E為一個(gè)具有 n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單圖 ， 若對(duì)于任意 u,v?V(u?v)， 既有有向邊u,v， 又有有向邊 v,u， 則稱 G為有向完全圖 ， 在不發(fā)生誤解的情況下 ， 也記為 Kn。 2nP2nC 122022/2/13 計(jì)算機(jī)學(xué)院 48/172 補(bǔ)圖 ? 設(shè) G＝ V， E為具有 n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖 ,從完全圖 Kn中 刪去 G中的所有邊而得到的圖稱為 G相對(duì)于完全圖 Kn的補(bǔ)圖 ， 簡(jiǎn)稱 G的 補(bǔ)圖 ， 記為 。 如果 X中的每一個(gè)結(jié)點(diǎn)與 Y中的全部結(jié)點(diǎn)都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計(jì)算機(jī)學(xué)院 56/172 例 G1≌ G2： a→v 1， b→v 2， c→v 3， d→v 4， e→v 5 a b d c e v4 v1 v3 v2 v5 G1 G2 a b d c e G3 G4 v4 v1 v3 v2 v5 G3≌G 4： a→v 1， b→v 4，c→v 2， d→v 5，e→v 3； 2022/2/13 計(jì)算機(jī)學(xué)院 57/172 例 G5≌ G6： a→v 1， b→v 2， c→v 3， d→v 4， e→v 7， f→v 6， g→v 9， h→v 8， i→v 5， j→v 10 a b d c e f g j h i G5 G6 v8 v1 v10 v2 v7 v3 v4 v5 v6 v9 彼得森圖 2022/2/13 計(jì)算機(jī)學(xué)院 58/172 兩個(gè)圖同構(gòu)的必要條件 1) 結(jié)點(diǎn)數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。 其余結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn) 。 ?v0和 vk分別稱為此道路的 起點(diǎn) 和 終點(diǎn) ， 統(tǒng)稱為道路的 端點(diǎn) 。 為什么 ？ 2022/2/13 計(jì)算機(jī)學(xué)院 69/172 簡(jiǎn)單道路與基本道路 ?若道路中的所有邊 e1， e2， … ， ek（ 有向邊 ）互不相同 ， 則稱此道路為簡(jiǎn)單道路；閉的簡(jiǎn)單道路稱為回路 。 2022/2/13 計(jì)算機(jī)學(xué)院 74/172 注： 1) 在 不 會(huì) 引 起 誤 解 的 情 況 下 ， 一 條 道 路v0e1v1e2v2… envn也可以用邊的序列 e1e2… en來(lái)表示 ， 這種表示方法對(duì)于有向圖來(lái)說(shuō)較為方便 。 ?若一個(gè)圖能以一個(gè)圈表示出來(lái) ， 則稱此圖為 圈圖 。 此通路上有 k+1個(gè)結(jié)點(diǎn) 。 若 k≤n 1，這條道路即為所求 。 若 k＞ n－ 1， 則此道路上的結(jié)點(diǎn)數(shù) k+1＞ n， 必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn) ， 設(shè) vis=vit，其中 ， 0≤s ＜ t≤k 。 去掉 vis到 vit中間的道路 ， 至少去掉一條邊 ， 得道路 vi0,vi1,… ,vis,vit+1,… vik， 此道路比原道路的長(zhǎng)度至少少 1。 如此重復(fù)進(jìn)行下去 ， 必可得一條從 vi到 vj不多于 n1條邊的道路 。 ■ 2022/2/13 計(jì)算機(jī)學(xué)院 84/172 167。對(duì)任意結(jié)點(diǎn) u， 規(guī)定 u～ u。 ?我們可以利用連通關(guān)系對(duì) G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分 : {V1， V2， … ， Vk}（ 顯然 ， Vi是一個(gè)等價(jià)類 ） ， 使得 G中 的任意兩個(gè)結(jié)點(diǎn) u和 v連通當(dāng)且僅當(dāng) u和 v同屬于一個(gè) Vi(1≤i≤k) 。 ?無(wú)向完全圖 Kn（ n≥ 1） 都是連通圖 ， 而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖 。 d(vi， vj)滿足下列性質(zhì)： ① d(vi,vj)≥ 0； （ 非負(fù)性 ） ② d(vi,vi)＝ 0； （ 對(duì)稱性 ） ③ d(vi,vk)+d(vk， vj)≥d(v i， vj)。 特別地 ， 若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn) v，則稱 v為割點(diǎn) 。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 2022/2/13 計(jì)算機(jī)學(xué)院 99/172 邊割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 2022/2/13 計(jì)算機(jī)學(xué)院 101/172 邊割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 又若 ?(G)≥k ， 則稱 G為 k連通圖 。 規(guī)定非連通圖的邊連通度為 0。 2022/2/13 計(jì)算機(jī)學(xué)院 107/172 例 ? 右圖所示圖的點(diǎn)連通度為 1，它是 1連通圖 ， 但不是 2連通圖；它的邊連通度為 1， 它是 1邊 連通圖 ， 但不是 2邊 連通圖 。 割點(diǎn) v是圖中任何道路的必經(jīng)之處！ “一夫當(dāng)關(guān)，萬(wàn)夫莫開” 2022/2/13 計(jì)算機(jī)學(xué)院 111/172 ?定理 在非平凡連通圖 G中 ， 結(jié)點(diǎn) v為 G的割點(diǎn)的充分必要條件是存在結(jié)點(diǎn) u和 w， 使 u到 w的每一條道路都以 v為內(nèi)部結(jié)點(diǎn) 。 為什么 ？ 理由： ?(G)≤?(G) 2022/2/13 計(jì)算機(jī)學(xué)院 114/172 ?定理 ： 對(duì)任意無(wú)向圖 G＝ V,E， 均有下面不等式成立：?(G)≤ ?(G)≤ ?(G)。 v3 v1 v4 v2 2022/2/13 計(jì)算機(jī)學(xué)院 116/172 有向圖的連通性 ?定義 u,v為有向圖 G＝ V,E中的兩個(gè)結(jié)點(diǎn) ， 若存在從結(jié)點(diǎn) u到結(jié)點(diǎn) v的道路 ， 則稱從結(jié)點(diǎn) u到結(jié)點(diǎn) v是可達(dá)的 ， 記為 u→v 。 ?有向圖結(jié)點(diǎn)之間的可達(dá)關(guān)系具有 自反性 和 傳遞性 ， 但一般說(shuō)來(lái) ， 可達(dá)關(guān)系 沒(méi)有對(duì)稱性 。 ?推論 ：對(duì)任意無(wú)向圖 G＝ V,E， 若 G是 k連通圖 ， 則 G必為 k邊 連通圖 。 （ 證明略 ， p212） 2022/2/13 計(jì)算機(jī)學(xué)院 112/172 ?定理 ： 對(duì)任意無(wú)向圖 G＝ V,E， 均有下面不等式成立： ?(G)≤ ?(G)≤ ?(G)。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 2022/2/13 計(jì)算機(jī)學(xué)院 108/172 例 ? 右圖所示圖的點(diǎn)連通度為 1，它是 1連通圖 ， 但不是 2連通圖；它的邊連通度為 1， 它是 1邊 連通圖 ， 但不是 2邊 連通圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 106/172 點(diǎn)連通度、邊連通度 ? 定義 1) 設(shè)無(wú)向圖連通圖 G＝ V,E， 稱 ?(G)＝ min{|V?||V?為 G的點(diǎn)割集 }為 G的點(diǎn)連通度 ， 簡(jiǎn)稱連通度 。 規(guī)定非連通圖的邊連通度為 0。 特別地 ， 若割集中只有一條邊 e， 則稱 e為割邊 。 特別地 ， 若割集中只有一條邊 e， 則稱 e為割邊 。 2022/2/13 計(jì)算機(jī)學(xué)院 9