離散數(shù)學第七章圖的基本概念知識點總結

1、本文格式為Word版，下載可任意編輯 離散數(shù)學第七章圖的基本概念知識點總結 1 / 13 圖論部分 第七章、圖的基本概念 7.1 無向圖及有向圖 無向圖與有向圖 多重集合: 元素可以重復出現(xiàn)的集合 無序積: A 若v i = v j , 則稱e k 為環(huán), 此時稱e k 與v i 的關聯(lián)次數(shù)為2; 若v i 不是e k 端點 , 2 / 1 3 則稱e k 與v i 的關聯(lián)次數(shù)為0. 無邊關聯(lián)的頂點稱作孤立點. 定義 設無向圖G =, v i ,v j V , e k ,e l E , 若(v i ,v j ) E , 則稱v i ,v j 相鄰; 若e k ,e l 至少有一個公共端點, 則

2、稱e k ,e l 相鄰. 對有向圖有類似定義. 設e k =?v i ,v j ?是有向圖的一條邊,又稱v i 是e k 的始點, v j 是e k 的終點, v i 鄰接到v j , v j 鄰接于v i . 鄰域和關聯(lián)集 頂點的度數(shù) 設G =為無向圖, v V , v 的度數(shù)(度) d (v ): v 作為邊的端點次數(shù)之和 懸掛頂點: 度數(shù)為1的頂點 懸掛邊: 與懸掛頂點關聯(lián)的邊 G 的最大度?(G )=maxd (v )| v V G 的最小度(G )=mind (v )| v V 例如 d (v 5)=3, d (v 2)=4, d (v 1)=4,?(G )=4, (G )=1,v

3、 4是懸掛頂點, e 7是懸掛邊, e 1是環(huán) 設D =為有向圖, v V , v 的出度d +(v ): v 作為邊的始點次數(shù)之和 v 的入度d -(v ): v 作為邊的終點次數(shù)之和 v 的度數(shù)(度) d (v ): v 作為邊的端點次數(shù)之和 d (v )= d +(v )+ d -(v ) D 的最大出度?+(D ), 最小出度+(D ) 最大入度?-(D ), 最小入度-(D ) 最大度?(D ), 最小度(D ) 例如 d +(a )=4, d -(a )=1, d (a )=5, d +(b )=0, d -(b )=3, d (b )=3, 3 / 13 ?+(D )=4, +(

4、D )=0, ?-(D )=3, -(D )=1, ?(D )=5, (D )=3. 握手定理 定理 任意無向圖和有向圖的所有頂點度數(shù)之和都等于邊數(shù)的2倍, 并且有向圖的所有頂點入度之和等于出度之和等于邊數(shù). 證 G 中每條邊（包括環(huán)）均有兩個端點，所以在計算G 中各頂點度數(shù)之和時，每條邊均提供2度，m 條邊共提供2m 度. 有向圖的每條邊提供一個入度和一個出度, 故所有頂點入度之和等于出度之和等于邊數(shù). 圖的度數(shù)列 設無向圖G 的頂點集V =v 1, v 2, , v n G 的度數(shù)列: d (v 1), d (v 2), , d (v n ) 如右圖度數(shù)列:4,4,2,1,3 設有向圖D

5、的頂點集V =v 1, v 2, , v n D 的度數(shù)列: d (v 1), d (v 2), , d (v n ) D 的出度列: d +(v 1), d +(v 2), , d +(v n ) D 的入度列: d -(v 1), d -(v 2), , d -(v n ) 如右圖度數(shù)列:5,3,3,3 出度列:4,0,2,1 入度列 :1,3,1,2 例1 (3,3,3,4), (2,3,4,6,8)能成為圖的度數(shù)列嗎? 解不可能. 它們都有奇數(shù)個奇數(shù). 例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小于等于2, 問G 至少有多少個頂點? 解設G有n個頂點. 由握手定理,

6、4?3+2?(n-4)2?10 解得n8 例3 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體. 證用反證法. 假設存在這樣的多面體, 作無向圖G=, 其中V=v | v為多面體的面, E=(u,v) | u,vVu與v有公共的棱uv. 根據(jù)假設, |V|為奇數(shù)且?vV, d(v)為奇數(shù). 這與握手定理的推論矛盾. 多重圖與簡單圖 定義 (1) 在無向圖中,假如有2條或2條以上的邊關聯(lián)同一對頂點, 則稱這些邊為平行邊, 平行邊的條數(shù)稱為重數(shù). (2)在有向圖中,假如有2條或2條以上的邊具有一致的始點和終點, 則稱這些邊為有向平行邊, 簡稱平行邊, 平行邊的條數(shù)稱為重數(shù). (3) 含平行邊

7、的圖稱為多重圖. (4) 既無平行邊也無環(huán)的圖稱為簡單圖. 注意:簡單圖是極其重要的概念 圖的同構 定義設G1=, G2=為兩個無向圖(有 4 / 13 5 / 13 向圖), 若存在雙射函數(shù) f : V 1V 2, 使得對于任意的 v i ,v j V 1, (v i ,v j )E 1（E 1）當且僅當 (f (v i ),f (v j )E 2（E 2）， 并且, (v i ,v j )（）與 (f (v i ),f (v j )（） 的重數(shù)一致，則稱G 1與G 2是同構的，記作G 1?G 2. 幾點說明： 圖之間的同構關系具有自反性、對稱性和傳遞性. 能找到多條同構的必要條件, 但它們

8、都不是充分條件: 邊數(shù)一致，頂點數(shù)一致 度數(shù)列一致(不計度數(shù)的順序) 對應頂點的關聯(lián)集及鄰域的元素個數(shù)一致，等等 若破壞必要條件，則兩圖不同構 至今沒有找到判斷兩個圖同構的多項式時間算法 完全圖：n 階無向完全圖K n : 每個頂點都與其余頂點相鄰的n 階無向簡單圖. 簡單性質: 邊數(shù)m =n (n -1)/2, ?=n -1 n 階有向完全圖: 每對頂點之間均有兩條方向相反的有向邊的n 階有向簡單圖. 簡單性質: 邊數(shù)m =n (n -1), ?=2(n -1), ?+=+=?-=-=n -1 子圖：定義設G=, G =是兩個圖 (1) 若V ?V且E ?E,則稱G 為G的子圖, G為G 的

9、 母圖, 記作G ?G (2) 若G ?G 且V =V，則稱G 為G的生成子圖 (3) 若V ?V 或E ?E，稱G 為G的真子圖 (4) 設V ?V 且V ?, 以V 為頂點集, 以兩端點都在 V 中的所有邊為邊集的G的子圖稱作V 的導 出子圖，記作GV (5) 設E ?E且E ?, 以E 為邊集, 以E 中邊關聯(lián)的 所有頂點為頂點集的G的子圖稱作E 的導出子 圖, 記作GE 補圖：定義設G=為n階無向簡單圖，以V為頂點集,所有使G成為完全圖K n的添加邊組成的集合為邊集的圖，稱為G的補圖，記作 . 若G? , 則稱G是自補圖. 例對上一頁K4的所有非同構子圖, 指出互為補圖的每一對子圖,

10、并指出哪些是自補圖. 7.2 通路、回路、圖的連通性 簡單通(回)路, 初級通(回)路, 繁雜通(回)路 定義給定圖G=（無向或有向的），G中頂點與邊的交替序列=v0e1v1e2e l v l， (1) 若?i(1il), v i-1, v i是e i的端點(對于有向圖, 要求v i-1是始點, v i是終點), 則稱為通路, v0是通路的起點, v l是通路的終點, l為通路的長度. 又若v =v l，則稱為回路. (2) 若通路(回路)中所有頂點(對于回路, 除v0=v l)各異，則稱為初級通路(初級回路).初級通路又稱作路徑, 初級回路又稱作圈. (3) 若通路(回路)中所有邊各異, 則

11、稱為簡單通路(簡單回路), 否則稱為繁雜通路(繁雜回路). 說明: 表示方法 用頂點和邊的交替序列(定義), 如=v0e1v1e2e l v l 6 / 13 用邊的序列, 如=e1e2e l 簡單圖中, 用頂點的序列, 如=v0v1v l 非簡單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5 環(huán)是長度為1的圈, 兩條平行邊構成長度為2的圈. 在無向簡單圖中, 所有圈的長度3; 在有向簡單圖中, 所有圈的長度2. 在兩種意義下計算的圈個數(shù) 定義意義下 在無向圖中, 一個長度為l(l3)的圈看作2l個不同的圈. 如v0v1v2v0 , v 1v 2 v v 1 , v2v0v1v2,

12、 v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6個不同的圈. 在有向圖中, 一個長度為l(l3)的圈看作l個不同的圈. 同構意義下 所有長度一致的圈都是同構的, 因而是1個圈. 定理在n階圖G中，若從頂點v i到v j（v iv j）存在通 路，則從v i到v j存在長度小于等于n-1的通路. 推論在n階圖G中，若從頂點v i到v j（v iv j）存在通 路，則從v i到v j存在長度小于等于n-1的初級通路. 定理在一個n階圖G中，若存在v i到自身的回路，則 一定存在v i到自身長度小于等于n的回路. 推論在一個n階圖G中，若存在v i到自身的簡單回 路，則一定存在長度小于等于n的初級回路. 無向圖的連通性 設無向圖G=, u與v連通: 若u與v之間有通路. 規(guī)定u與自身總連通. 連通關系R=| u,vV且uv是V上的等價關系 連通圖:任意