ppt25---圖的頂點(diǎn)著色-資料下載頁
2025-08-16 01:31本頁面
【正文】 (1, 3) 與 H(2, 4) 的交叉點(diǎn)。因此， п 可以擴(kuò)充為 G的 5正常頂點(diǎn)著色。 1 0 x t 0 1 2 ?1 ? 0 1 n 31 (四 )、頂點(diǎn)著色的應(yīng)用 圖的正常頂點(diǎn)著色對(duì)應(yīng)的實(shí)際問題是“劃分”問題。 例 1 課程安排問題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開設(shè)的課程為：圖論 (GT), 統(tǒng)計(jì)學(xué) (S),線性代數(shù) (LA), 高等微積分 (AC), 幾何學(xué) (G), 和近世代數(shù) (MA)?，F(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。 1 0 x t 0 1 2 ?1 ? 0 1 n 32 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 33 如果我們用同一顏色給同一時(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. 1 0 x t 0 1 2 ?1 ? 0 1 n 34 (2) 求安排 具體著色 GT MA G AC LA S 選課狀態(tài)圖 1 0 x t 0 1 2 ?1 ? 0 1 n 35 例 2 交通燈的相位設(shè)置問題：如圖所示，列出了繁華街道路口處的交通車道 L1,L2,…,L9 。在此路口處安置了交通燈。當(dāng)交通燈處于某個(gè)相位時(shí)，亮綠燈的車道上的車輛就可以安全通過路口。為了 (最終 )讓所有的車輛都能夠安全通過路口，對(duì)于交通燈來說，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 1 0 x t 0 1 2 ?1 ? 0 1 n 36 解：車道模型為頂點(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 37 另一方面，通過嘗試，用 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 38 第二次上交作業(yè) 習(xí)題 1 ： 4， 5, 11， 12, 17， 18. 習(xí)題 2 ： 1， 9, 16. 習(xí)題 3 ： 1， 3, 7, 12， 13. 作成 Word文檔上交。 1 0 x t 0 1 2 ?1 ? 0 1 n 39 作業(yè) P187190 習(xí)題 7 ： 79 1 0 x t 0 1 2 ?1 ? 0 1 n 40 Thank You
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1