期末復(fù)習(xí)ppt課件-資料下載頁
2025-04-29 02:55本頁面
【正文】 ，所以需要的教室數(shù)為 240/40=6。 1 0 x t 0 1 2 ?1 ? 0 1 n 37 例 3 (比賽安排問題 ) Alvin (A)曾邀請 3對夫婦到他的避暑別墅住一個(gè)星期。他們是： Bob和 Carrie , David和 Edith, Frank和 Gena。由于這 6人都喜歡網(wǎng)球運(yùn)動(dòng)，所以他們決定進(jìn)行網(wǎng)球比賽。 6位客人的每一位都要和其配偶之外的每位客人比賽。另外， Alvin將分別和 David， Edith， Frank， Gena進(jìn)行一場比賽。若沒有人在同一天進(jìn)行 2場比賽，則要在最少天數(shù)完成比賽，如何安排？ 解：用點(diǎn)表示參賽人，兩點(diǎn)連線當(dāng)且僅當(dāng)兩人有比賽。這樣得到比賽狀態(tài)圖。 問題對應(yīng)于求狀態(tài)圖的一種最優(yōu)邊著色 (用最少色數(shù)進(jìn)行正常邊著色 )。 1 0 x t 0 1 2 ?1 ? 0 1 n 38 狀態(tài)圖為： F D A G C E B 圖 G 由于 n=2 3+1, 所以 k=3。而 Δ=5 ， m=163 5=kΔ,所以由定理 5知： ( )= 6G?? 1 0 x t 0 1 2 ?1 ? 0 1 n 39 最優(yōu)著色為： F D A G C E B 圖 G 1 0 x t 0 1 2 ?1 ? 0 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)著色問題 1 0 x t 0 1 2 ?1 ? 0 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)圖 1 0 x t 0 1 2 ?1 ? 0 1 n 42 如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求對應(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. 1 0 x t 0 1 2 ?1 ? 0 1 n 43 (2) 求安排 具體著色 GT MA G AC LA S 選課狀態(tài)圖 1 0 x t 0 1 2 ?1 ? 0 1 n 44 例 5 交通燈的相位設(shè)置問題：如圖所示，列出了繁華街道路口處的交通車道 L1,L2,…,L9 。在此路口處安置了交通燈。當(dāng)交通燈處于某個(gè)相位時(shí)，亮綠燈的車道上的車輛就可以安全通過路口。為了 (最終 )讓所有的車輛的燈都能夠安全通過路口，對于交通燈來說，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 1 0 x t 0 1 2 ?1 ? 0 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 1 0 x t 0 1 2 ?1 ? 0 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 1 0 x t 0 1 2 ?1 ? 0 1 n 47 Thank You
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1