圖論30電子科大楊春-資料下載頁
2025-01-02 13:43本頁面
【正文】 客人比賽。另外， Alvin將分別和 David， Edith， Frank， Gena進(jìn)行一場比賽。若沒有人在同一天進(jìn)行 2場比賽，則要在最少天數(shù)完成比賽，如何安排？ 解：用點表示參賽人，兩點連線當(dāng)且僅當(dāng)兩人有比賽。這樣得到比賽狀態(tài)圖。 問題對應(yīng)于求狀態(tài)圖的一種最優(yōu)邊著色 (用最少色數(shù)進(jìn)行正常邊著色 )。 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。而 Δ=5 ， m=163 5=kΔ,所以由定理 5知： ( )= 6G??38 1 0 x t 0 1 2 ?1 ? 0 1 n 最優(yōu)著色為： F D A G C E B 圖 G 39 1 0 x t 0 1 2 ?1 ? 0 1 n 例 4 課程安排問題：某大學(xué)數(shù)學(xué)系要為這個夏季安排課程表。所要開設(shè)的課程為：圖論 (GT), 統(tǒng)計學(xué) (S),線性代數(shù) (LA), 高等微積分 (AC), 幾何學(xué) (G), 和近世代數(shù) (MA)?，F(xiàn)有 10名學(xué)生 (如下所示 )需要選修這些課程。根據(jù)這些信息，確定開設(shè)這些課程所需要的最少時間段數(shù)，使得學(xué)生選課不會發(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)、 點著色問題 40 1 0 x t 0 1 2 ?1 ? 0 1 n A10: GT, S。 解：把課程模型為圖 G的頂點，兩頂點連線當(dāng)且僅當(dāng)有某個學(xué)生同時選了這兩門課程。 GT MA G AC LA S 選課狀態(tài)圖 41 1 0 x t 0 1 2 ?1 ? 0 1 n 如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求對應(yīng)于點色數(shù)的著色。 (1) 求點色數(shù) 一方面，因圖中含有奇圈 (紅色邊 ), 所以，點色數(shù)至少為 3。又因為點 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 交通燈的相位設(shè)置問題：如圖所示，列出了繁華街道路口處的交通車道 L1,L2,…,L9 。在此路口處安置了交通燈。當(dāng)交通燈處于某個相位時，亮綠燈的車道上的車輛就可以安全通過路口。為了 (最終 )讓所有的車輛的燈都能夠安全通過路口，對于交通燈來說，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 44 1 0 x t 0 1 2 ?1 ? 0 1 n 解：車道模型為頂點，兩點連線當(dāng)且僅當(dāng)兩個車道上的車不能同時安全地進(jìn)入路口。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 問題轉(zhuǎn)化為求 G的點色數(shù)。一方面， G中含有 K4,所以，點色數(shù)至少為 4； L9 L8 L7 L6 L5 L4 L3 L2 L1 G 45 1 0 x t 0 1 2 ?1 ? 0 1 n 另一方面，通過嘗試，用 4種色實現(xiàn)了正常點著色。 所以，最小相位為 4。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 2 1 1 2 2 4 3 4 3 46 1 0 x t 0 1 2 ?1 ? 0 1 n 第三次作業(yè) 請舉例說明最短路算法應(yīng)用、最小生成樹應(yīng)用、偶圖匹配應(yīng)用、平面圖應(yīng)用、邊著色應(yīng)用、點著色應(yīng)用。 時間： 兩周內(nèi)。 47 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號-1