【正文】 時間： 兩周內(nèi)。 所以，最小相位為 4。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 問題轉(zhuǎn)化為求 G的點色數(shù)。當交通燈處于某個相位時，亮綠燈的車道上的車輛就可以安全通過路口。又因為點 LA與該圈上每一個點均鄰接，所以，點色數(shù)至少為 4. GT MA G AC LA S 選課狀態(tài)圖 另一方面，我們用 4種色實現(xiàn)了 G的正常點著色，所以，圖的點色數(shù)為 4. 42 1 0 x t 0 1 2 ?1 ? 0 1 n (2) 求安排 具體著色 GT MA G AC LA S 選課狀態(tài)圖 43 1 0 x t 0 1 2 ?1 ? 0 1 n 例 5 交通燈的相位設置問題：如圖所示，列出了繁華街道路口處的交通車道 L1,L2,…,L9 。 GT MA G AC LA S 選課狀態(tài)圖 41 1 0 x t 0 1 2 ?1 ? 0 1 n 如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求對應于點色數(shù)的著色。 2)、 點著色問題 40 1 0 x t 0 1 2 ?1 ? 0 1 n A10: GT, S。 A8: LA,GT, S 。 A6: G, AC。 A4: G, LA, AC 。 A2: MA, LA, G 。根據(jù)這些信息，確定開設這些課程所需要的最少時間段數(shù)，使得學生選課不會發(fā)生沖突。所要開設的課程為：圖論 (GT), 統(tǒng)計學 (S),線性代數(shù) (LA), 高等微積分 (AC), 幾何學 (G), 和近世代數(shù) (MA)。 37 1 0 x t 0 1 2 ?1 ? 0 1 n 狀態(tài)圖為： F D A G C E B 圖 G 由于 n=2 3+1, 所以 k=3。這樣得到比賽狀態(tài)圖。另外， Alvin將分別和 David， Edith， Frank， Gena進行一場比賽。由于這 6人都喜歡網(wǎng)球運動，所以他們決定進行網(wǎng)球比賽。 36 1 0 x t 0 1 2 ?1 ? 0 1 n 例 3 (比賽安排問題 ) Alvin (A)曾邀請 3對夫婦到他的避暑別墅住一個星期。平均每天要安排 7節(jié)課。由于 G是偶圖，所以邊色數(shù)為 G的最大度 35。求： (1) 一天分成幾節(jié)課，才能滿足所提出的要求？ (2) 若安排出每天 8節(jié)課的時間表，需要多少間教室？ 35 1 0 x t 0 1 2 ?1 ? 0 1 n 3233333333331 3 6 0 4 2 5 1 3 3 0 45055005050552424242424233 5 2 2 0 3 1 4 4 3 2 55500550505500 3 4 3 4 3 4 3 4 3 3 0P????? ??????x1 x2 x3 x4 x6 x5 x7 y2 y1 y8 y7 y6 y5 y4 y3 y10 y9 y11 y12 解：問題可模型為一個偶圖。 著色問題 1)、 邊著色問題 例 2 (排課表問題 ) 在一個學校中，有 7個教師 12個班級。 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中頂點連線當且僅當學生申請了該工作。 G : d, e, f, g 。 E : a, c, d, f 。 C : b, e 。每名學生申請的職位如下： A : b, c 。 []i ixk? 1根樹問題 定理 32 在完全 m元樹 T中，若樹葉數(shù)為 t , 分支點數(shù)為 i , 則： ( 1 ) 1m i t? ? ?31 1 0 x t 0 1 2 ?1 ? 0 1 n (三 )、圖論應用 偶圖匹配問題 例 1 有 7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。若 G中只有一個最大度點或恰有兩個相鄰的最大度點，則： ( ) ( )GG? ? ??28 1 0 x t 0 1 2 ?1 ? 0 1 n 定理 28 設 G是單圖。 4)、對偶圖的性質(zhì) 定理 22 平面圖 G的對偶圖必然連通 . 5)、極大平面圖的性質(zhì) 定理 23 設 G是至少有 3個頂點的平面圖，則 G是極大平面圖，當且僅當 G的每個面的次數(shù)是 3且為單圖。 定理 19 每個沒有割邊的 3正則圖是一個 1因子和 1個 2因子之和。 定理 17 K2n+1可 2因子分解。 定理 15 K2n可一因子分解。若 n≧3 且 1( ) 12nEG ????????? 則 G是 H圖；并且，具有 n個頂點