圖論25電子科大楊春-資料下載頁(yè)
2025-01-05 13:02本頁(yè)面
【正文】 1 0 x t 0 1 2 ?1 ? 0 1 n (四 )、頂點(diǎn)著色的應(yīng)用 圖的正常頂點(diǎn)著色對(duì)應(yīng)的實(shí)際問(wèn)題是“劃分”問(wèn)題。 例 1 課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開(kāi)設(shè)的課程為：圖論 (GT), 統(tǒng)計(jì)學(xué) (S),線性代數(shù) (LA), 高等微積分 (AC), 幾何學(xué) (G), 和近世代數(shù) (MA)。現(xiàn)有 10名學(xué)生 (如下所示 )需要選修這些課程。根據(jù)這些信息，確定開(kāi)設(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。 31 1 0 x t 0 1 2 ?1 ? 0 1 n A10: GT, S。 解：把課程模型為圖 G的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門(mén)課程。 GT MA G AC LA S 選課狀態(tài)圖 32 1 0 x t 0 1 2 ?1 ? 0 1 n 如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問(wè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. 33 1 0 x t 0 1 2 ?1 ? 0 1 n (2) 求安排 具體著色 GT MA G AC LA S 選課狀態(tài)圖 34 1 0 x t 0 1 2 ?1 ? 0 1 n 例 2 交通燈的相位設(shè)置問(wèn)題：如圖所示，列出了繁華街道路口處的交通車(chē)道 L1,L2,…,L9 。在此路口處安置了交通燈。當(dāng)交通燈處于某個(gè)相位時(shí)，亮綠燈的車(chē)道上的車(chē)輛就可以安全通過(guò)路口。為了 (最終 )讓所有的車(chē)輛都能夠安全通過(guò)路口，對(duì)于交通燈來(lái)說(shuō)，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 35 1 0 x t 0 1 2 ?1 ? 0 1 n 解：車(chē)道模型為頂點(diǎn)，兩點(diǎn)連線當(dāng)且僅當(dāng)兩個(gè)車(chē)道上的車(chē)不能同時(shí)安全地進(jìn)入路口。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 問(wèn)題轉(zhuǎn)化為求 G的點(diǎn)色數(shù)。一方面， G中含有 K4,所以，點(diǎn)色數(shù)至少為 4； L9 L8 L7 L6 L5 L4 L3 L2 L1 G 36 1 0 x t 0 1 2 ?1 ? 0 1 n 另一方面，通過(guò)嘗試，用 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 37 1 0 x t 0 1 2 ?1 ? 0 1 n 作業(yè) P187190 習(xí)題 7 ： 79 38 1 0 x t 0 1 2 ?1 ? 0 1 n Thank You ! 39 1 0 x t 0 1 2 ?1 ? 0 1 n 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1