《電子科技大學圖論總復習PPT.ppt》由會員分享，可在線閱讀，更多相關《電子科技大學圖論總復習PPT.ppt（47頁珍藏版）》請在裝配圖網上搜索。
1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1 圖論及其應用 復習課件 數(shù)學科學學院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本次課主要內容 (二 )、重要結論 期末復習 (一 )、重點概念 (三 )、應用 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 (一 )、重點概念 1、
2、圖、簡單圖、圖的同構與自同構、度序列與圖序列、 補圖與自補圖、兩個圖的聯(lián)圖、兩個圖的積圖、偶圖； (1) 圖：一個圖是一個序偶 ，記為 G=(V,E),其中： 1) V是一個有限的非空集合，稱為頂點集合 ,其元素稱為頂點或點。 用 |V|表示頂點數(shù)； 2) E是由 V中的點組成的無序對構成的集合，稱為邊集，其元素稱 為邊，且同一點對在 E中可以重復出現(xiàn)多次。用 |E|表示邊數(shù)。 (2) 簡單圖：無環(huán)無重邊的圖稱為簡單圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 (3) 圖的
3、度序列： 一個圖 G的各個點的度 d1, d2,, dn構成的非負整數(shù)組 (d1, d2,, dn) 稱為 G的度序列 。 注：度序列的判定問題是重點。 (4) 圖的圖序列： 一個非負數(shù)組如果是某簡單圖的度序列，我們稱它為可圖序列，簡 稱圖序列。 注：圖序列的判定問題是重點。 (5) 圖的同構： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 設有兩個圖 G1=(V1,E1)和 G2=(V2,E2),若在其頂點集合間存在雙射，使得邊 之間存在如下關系：設 u1
4、u 2v1v 2, u1,v1 V1, u2,v2 V2; u1v1 E1,當 且僅當 u2v2 E2,且 u1v1與 u2v2的重數(shù)相同。稱 G1與 G2同構，記為： 12GG 例 1 指出 4個頂點的非同構的所有簡單圖。 分析：四個頂點的簡單圖最少邊數(shù)為 0，最多邊數(shù)為 6，所以 可按邊數(shù)進行枚舉。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 (6) 補圖與自補圖 1) 對于一個簡單圖 G =（ V, E），令集合 1 ,,E u v u v u
5、v V 則圖 H =（ V， E1E） 稱為 G的補圖，記為 HG 2) 對于一個簡單圖 G =（ V, E），若 ，稱 G為自補圖。 GG 注：要求掌握自補圖的性質。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 (7) 聯(lián)圖 設 G1,G2是兩個不相交的圖，作 G1+G2，并且將 G1中每個頂點和 G2 中的每個頂點連接，這樣得到的新圖稱為 G1與 G2的聯(lián)圖。記為 ： 12GG (8) 積圖 設
6、 是兩個圖。對點集 1 1 1 2 2 2( , ) , ( , ) ,G V E G V E 12V V V 的任意兩個點 u=(u1,u2)與 v=(v1,v2),當 (u1=v1和 u2adjv2)或 (u2=v2和 u1adjv1)時， 把 u與 v相連。如此得到的新圖稱為 G1與 G2的積圖。 記為 12G G G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 (9) 偶圖 所謂具有二分類（ X, Y）的偶圖（或二部圖）是指一個圖，它的點 集可以分解為兩個 (非空 )子集 X
7、和 Y，使得每條邊的一個端點在中，另 一個端點在 Y中 . 注 : 掌握偶圖的判定。 2、樹、森林，生成樹，最小生成樹、根樹、完全 m元樹。 (1) 樹 不含圈的圖稱為無圈圖，樹是連通的無圈圖。 (2) 森林 稱無圈圖 G為森林。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 (3) 生成樹 圖 G的一個生成子圖 T如果是樹，稱它為 G的一棵生成樹；若 T 為森林，稱它為 G的一個生成森林。 生成樹的邊稱為樹枝， G中非生成樹的邊稱為弦。 (4) 最小生成
8、樹 在連通邊賦權圖 G中求一棵總權值最小的生成樹。該生成樹稱 為最小生成樹或最小代價樹。 注：要求熟練掌握最小生成樹的求法。 (5) 根樹 一棵非平凡的有向樹 T，如果恰有一個頂點的入度為 0，而其余所有頂 點的入度為 1，這樣的的有向樹稱為根樹。其中入度為 0的點稱為樹根， 出度為 0的點稱為樹葉，入度為 1，出度大于 1的點稱為內點。又將內點 和樹根統(tǒng)稱為分支點。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 (6) 完全 m元樹 對于根樹 T，若每個分支點至
9、多 m個兒子，稱該根樹為 m元根樹； 若每個分支點恰有 m個兒子，稱它為完全 m元樹。 注：對于完全 m元樹，要弄清其結構。 3、途徑 (閉途徑 )，跡 (閉跡 ), 路 (圈 ), 最短路，連通圖，連 通分支，點連通度與邊連通度。 注：上面概念分別在 1和 3章 4、歐拉圖，歐拉環(huán)游，歐拉跡，哈密爾頓圈，哈密爾頓 圖，哈密爾頓路，中國郵路問題，最優(yōu) H圈。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 (1) 歐拉圖與歐拉環(huán)游 (2) 歐拉跡 對于連通圖 G，如果 G中存在經
10、過每條邊的閉跡，則稱 G為歐 拉圖，簡稱 G為 E圖。歐拉閉跡又稱為歐拉環(huán)游，或歐拉回路。 對于連通圖 G，如果 G中存在經過每條邊的跡，則稱該跡為 G 的一條歐拉跡。 (3) 哈密爾頓圖與哈密爾頓圈 如果經過圖 G的每個頂點恰好一次后能夠回到出發(fā)點，稱這樣 的圖為哈密爾頓圖，簡稱 H圖。所經過的閉途徑是 G的一個生成圈， 稱為 G的哈密爾頓圈。 (4) 哈密爾頓路 圖 G的經過每個頂點的路稱為哈密爾頓路。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 5、匹配、最大匹
11、配、完美匹配、最優(yōu)匹配、因子分解。 (1) 匹配 匹配 M--- 如果 M是圖 G的邊子集 (不含環(huán)），且 M中的任意兩條邊沒有 共同頂點，則稱 M是 G的一個匹配或對集或邊獨立集。 (2) 最大匹配與完美匹配 最大匹配 M--- 如果 M是圖 G的包含邊數(shù)最多的匹配，稱 M是 G的一個 最大匹配。特別是，若最大匹配飽和了 G的所有頂點，稱它為 G的一 個完美匹配。 (3) 最優(yōu)匹配 設 G=(X, Y)是邊賦權完全偶圖， G中的一個權值最大的完美匹配稱為 G 的最優(yōu)匹配。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5
12、 2 1 0.5 0 0.5 1 n 13 (4) 因子分解 所謂一個圖 G的因子分解，是指把圖 G分解為若干個邊不重的因子 之并。 注：要弄清楚因子分解和完美匹配之間的聯(lián)系與區(qū)別。 6、平面圖、極大平面圖、極大外平面圖、平面圖的對偶 圖。 (1) 平面圖： 如果能把圖 G畫在平面上，使得除頂點外，邊與邊之 間沒有交叉，稱 G可以嵌入平面，或稱 G是可平面圖?？善矫鎴D G的邊 不交叉的一種畫法，稱為 G的一種平面嵌入， G的平面嵌入表示的圖稱 為平面圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0
13、 0.5 1 n 14 (2) 極大平面圖 : 設 G是簡單可平面圖，如果 G是 Ki (1 i 4),或者在 G的任意非鄰接頂點間添加一條邊后，得到的圖均是非可平面圖， 則稱 G是極大可平面圖。 極大可平面圖的平面嵌入稱為極大平面圖。 (3) 極大外平面圖：若一個可平面圖 G存在一種平面嵌入，使得其所有 頂點均在某個面的邊界上，稱該圖為外可平面圖。外可平面圖的一種 外平面嵌入，稱為外平面圖。 (4) 平面圖的對偶圖：給定平面圖 G， G的對偶圖 G*如下構造： 1) 在 G的每個面 fi內取一個點 vi*作為 G*的一個頂點； 2) 對 G的一條邊 e, 若 e是面 fi
14、與 fj 的公共邊，則連接 vi*與 vj*，且連線 穿過邊 e;若 e是面 fi中的割邊，則以 vi為頂點作環(huán)，且讓它與 e相交 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 7、邊色數(shù)、點色數(shù)、色多項式 (1)、邊色數(shù) 設 G是圖，對 G進行正常邊著色需要的最少顏色數(shù)，稱為 G的邊色 數(shù)，記為： ()G (2)、點色數(shù) 對圖 G正常頂點著色需要的最少顏色數(shù)，稱為圖 G的點色數(shù)。圖 G的點色數(shù)用 表示。 ()G (3)、色多項式 對圖進行正常頂點著色，其方式數(shù)
15、 Pk(G)是 k的多項式，稱為圖 G 的色多項式。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 8、強連通圖、單向連通圖、弱連通圖 (1)、強連通圖 (2)、弱連通圖 (3)、單向連通圖 若 D的基礎圖是連通的，稱 D是弱連通圖； 若 D的中任意兩點是單向連通的，稱 D是單向連通圖。 若 D的中任意兩點是雙向連通的，稱 D是強連通圖； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n
16、17 (二 )、重要結論 1、握手定理及其推論 定理 1： 圖 G= (V, E)中所有頂點的度的和等于邊數(shù) m的 2倍，即： () ( ) 2 v V G d v m 推論 1 在任何圖中，奇點個數(shù)為偶數(shù)。 推論 2 正則圖的階數(shù)和度數(shù)不同時為奇數(shù) 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 2、托蘭定理 定理 2 若 n階簡單圖 G不包含 Kl+1，則 G度弱于某個完 全 l 部圖 H，且若 G具有與 H 相同的度序列，則 : GH 定理 3 設 T
17、是 (n, m)樹，則： 3、樹的性質 1mn 4、最小生成樹算法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 5、偶圖判定定理 定理 4 圖 G是偶圖當且僅當 G中沒有奇回路。 6、敏格爾定理 定理 5 (1) 設 x與 y是圖 G中的兩個不相鄰點，則 G中分離 點 x與 y的最小點數(shù)等于獨立的 (x, y)路的最大數(shù)目； (2)設 x與 y是圖 G中的兩個不相鄰點，則 G中分離點 x與 y的最小邊數(shù)等于 G中邊不重的 (x, y)路的最大數(shù)目。 7、歐拉圖、歐拉
18、跡的判定 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 定理 6 下列陳述對于非平凡連通圖 G是等價的： (1) G是歐拉圖； (2) G的頂點度數(shù)為偶數(shù)； (3) G的邊集合能劃分為圈。 推論： 連通非歐拉圖 G存在歐拉跡當且僅當 G中只有 兩個頂點度數(shù)為奇數(shù)。 8、 H圖的判定 定理 7 (必要條件 ) 若 G為 H圖，則對 V(G)的任一非空 頂點子集 S，有： ()G S S 0.8 1 0.6 0.4 0.2 0
19、x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 定理 8 (充分條件 ) 對于 n3 的單圖 G，如果 G中有： () 2nG 定理 9 (充分條件 ) 對于 n3 的單圖 G，如果 G中的任意 兩個不相鄰頂點 u與 v，有： ( ) ( )d u d v n 定理 10 (幫迪 閉包定理 ) 圖 G是 H圖當且僅當它的閉 包是 H圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 定理 11(Chvtal 度序列判定法 ) 設簡單圖 G的度
20、序列 是 (d1,d2,,d n), 這里， d1d 2d n,并且 n3. 若對任意 的 mm,或者 dn-m n -m,則 G是 H圖。 定理 12 設 G是 n階單圖。若 n3 且 1( ) 1 2 nEG 則 G是 H圖；并且，具有 n個頂點 條邊的非 H圖 只有 C1,n以及 C2,5. 1 1 2 n 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 8、偶圖匹配與因子分解 定理 13 (Hall定理）設 G=(X, Y)是偶圖，則 G存在飽和
21、X每個 頂點的匹配的充要條件是： , ( ) ( * )S X N S S 對有 推論：若 G是 k (k0)正則偶圖，則 G存在完美匹配。 定理 14 (哥尼， 1931) 在偶圖中，最大匹配的邊數(shù)等于最小 覆蓋的頂點數(shù)。 定理 15 K2n可一因子分解。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 定理 16 具有 H圈的三正則圖可一因子分解。 定理 17 K2n+1可 2因子分解。 定理 18 K2n可分解為一個 1因子和 n-1個 2因子之和。
22、 定理 19 每個沒有割邊的 3正則圖是一個 1因子和 1個 2因 子之和。 最優(yōu)匹配算法 (見教材） 9、平面圖及其對偶圖 1)、平面圖的次數(shù)公式 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 2)、平面圖的歐拉公式 定理 20 設 G=(n, m)是平面圖，則： d e g ( ) 2 f fm 定理 21(歐拉公式 ) 設 G=(n, m)是連通平面圖， 是 G的面 數(shù)，則： 2nm 3)、幾個重要推論 0.8 1
23、 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 推論 1 設 G是具有 n個點 m條邊 個面的連通平面圖，如 果對 G的每個面 f ,有： deg (f) l 3, 則： ( 2 )2lmnl 推論 2 設 G是具有 n個點 m條邊 個面的簡單平面圖， 則： 36mn 推論 3 設 G是具有 n個點 m條邊的簡單平面圖，則： 5 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 注：掌握證明方法。 4)、對偶圖的性
24、質 定理 22 平面圖 G的對偶圖必然連通 . 5)、極大平面圖的性質 定理 23 設 G是至少有 3個頂點的平面圖，則 G是極大 平面圖，當且僅當 G的每個面的次數(shù)是 3且為單圖。 10、著色問題 1)、邊著色 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 定理 24 ,()mnK 定理 25 (哥尼， 1916)若 G是偶圖，則 ()G 定理 26 (維津定理， 1964) 若 G是單圖，則： ( ) ( ) + 1GG 或 定理 2
25、7 設 G是單圖且 (G)0。若 G中只有一個最大度 點或恰有兩個相鄰的最大度點，則： ( ) ( )GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 定理 28 設 G是單圖。若點數(shù) n=2k+1且邊數(shù) mk ,則： ( ) ( ) 1GG 定理 29 設 G是奇數(shù)階 正則 單圖 ,若 0,則： ( ) ( ) 1GG 2)、點著色 定理 30 對任意的圖 G，有： ( ) ( ) 1GG 0.8 1 0.
26、6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 定理 31(布魯克斯， 1941) 若 G是連通的單圖，并且它 既不是奇圈，又不是完全圖，則： ( ) ( )GG 3)、色多項式 定理 32 設 G為簡單圖，則對任意 有： ()e E G ( ) ( ) ( )k k kP G P G e P G e 1)、遞推計數(shù)法 2)、理想子圖計數(shù)方法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 (1) 畫
27、出 G的補圖 G (2) 求出關于補圖的 ( ) , ( 1 ) iir N G i n (3) 寫出關于補圖的伴隨多項式 1 ( , ) n ii i h G x r x (4) 將 代入伴隨多項式中得到 Pk(G)。 i ixk 11、根樹問題 定理 32 在完全 m元樹 T中，若樹葉數(shù)為 t , 分支點數(shù)為 i , 則： ( 1 ) 1m i t 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 32 (三 )、圖論應用 1、
28、偶圖匹配問題 例 1 有 7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。就業(yè)處 提供的公開職位是：會計師 (a) ,咨詢師 (b),編輯 (c ),程序員 (d), 記者 (e), 秘書 (f)和教師 (g)。每名學生申請的職位如下： A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F : c, e ; G : d, e, f, g ; 問：學生能找到理想工作嗎？ 重點掌握如下兩方面應用 0.8 1 0.6
29、 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 33 問題轉化為是否有飽和 X每個頂點的一個匹配。 F E D C B A G a b c d e f g 解：如果令 X= A, B, C, D, E, F, G ,Y= a, b, c, d, e, f , g ,X中頂點與 Y中頂點連線當且僅當學生申請了該工作。于 是，得到反映學生和職位之間的狀態(tài)圖： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 34 當 S取 X中四元點集時，若取 S
30、= A,C,D,F ,則有 3=|N(S)|3 5=k,所以 由定理 5知： ( )= 6G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 39 最優(yōu)著色為： F D A G C E B 圖 G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 40 例 4 課程安排問題：某大學數(shù)學系要為這個夏季安排 課程表。所要開設的課程為：圖論 (GT), 統(tǒng)計學 (S),線性 代數(shù) (LA), 高等微積分 (A
31、C), 幾何學 (G), 和近世代數(shù) (MA)。 現(xiàn)有 10名學生 (如下所示 )需要選修這些課程。根據這些信 息，確定開設這些課程所需要的最少時間段數(shù)，使得學 生選課不會發(fā)生沖突。 (學生用 Ai表示） A1: LA, S ; A2: MA, LA, G ; A3: MA, G, LA; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA; 2)、 點著色問題 0.8 1 0.6 0.4 0.2 0 x t 0
32、0.5 1 1.5 2 1 0.5 0 0.5 1 n 41 A10: GT, S。 解：把課程模型為圖 G的頂點，兩頂點連線當且僅當 有某個學生同時選了這兩門課程。 GT MA G AC LA S 選課狀態(tài)圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 42 如果我們用同一顏色給同一時段的課程頂點染色，那 么，問題轉化為在狀態(tài)圖中求對應于點色數(shù)的著色。 (1) 求點色數(shù) 一方面，因圖中含有奇圈 (紅 色邊 ), 所以，點色數(shù)至少為 3。 又因為點 LA與該圈上每一個
33、點 均鄰接，所以，點色數(shù)至少為 4. GT MA G AC LA S 選課狀態(tài)圖 另一方面，我們用 4種色實現(xiàn)了 G的正常點著色，所以， 圖的點色數(shù)為 4. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 43 (2) 求安排 ----具體著色 GT MA G AC LA S 選課狀態(tài)圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 44 例 5 交通燈的相位設置問題：如圖所示，列出了繁華街
34、道 路口處的交通車道 L1,L2,,L9 。在此路口處安置了交通燈。 當交通燈處于某個相位時，亮綠燈的車道上的車輛就可以安 全通過路口。為了 (最終 )讓所有的車輛的燈都能夠安全通過 路口，對于交通燈來說，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 45 解：車道模型為頂點，兩點連線當且僅當兩個車道上的 車不能同時安全地進入路口。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 問題轉化為求
35、 G的點色數(shù)。一方面， G中含有 K4,所以， 點色數(shù)至少為 4； L9 L8 L7 L6 L5 L4 L3 L2 L1 G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 46 另一方面，通過嘗試，用 4種色實現(xiàn)了正常點著色。 所以，最小相位為 4。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 2 1 1 2 2 4 3 4 3 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 47 Thank You !
電子科技大學圖論總復習PPT.ppt
