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