圖論30電子科大楊春-閱讀頁
2025-01-12 13:43本頁面
【正文】 1 0 x t 0 1 2 ?1 ? 0 1 n (1) 畫出 G的補圖 G (2) 求出關于補圖的 ( ) , ( 1 )iir N G i n? ? ? (3) 寫出關于補圖的伴隨多項式 1( , ) n iiih G x r x?? ? (4) 將 代入伴隨多項式中得到 Pk(G)。就業(yè)處提供的公開職位是：會計師 (a) ,咨詢師 (b),編輯 (c ),程序員(d), 記者 (e), 秘書 (f)和教師 (g)。 B : a, b, d, f, g 。 D : b, c, e 。 F : c, e 。 問：學生能找到理想工作嗎？ 重點掌握如下兩方面應用 32 1 0 x t 0 1 2 ?1 ? 0 1 n 問題轉化為是否有飽和 X每個頂點的一個匹配。于是，得到反映學生和職位之間的狀態(tài)圖： 33 1 0 x t 0 1 2 ?1 ? 0 1 n 當 S取 X中四元點集時，若取 S=｛ A,C,D,F｝ ,則有3=|N(S)||S|=4 所以，不存在飽和 X每個頂點的匹配。在每周 5天教學日條件下，教課的要求由如下矩陣給出： 34 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 其中， pij表示 xi必須教 yj班的節(jié)數(shù)。 一節(jié)課對應邊正常著色的一個色組。這樣，最少總課時為 35節(jié)課。 如果每天安排 8節(jié)課，因為 G的總邊數(shù)為 240，所以需要的教室數(shù)為 240/40=6。他們是： Bob和 Carrie , David和 Edith, Frank和 Gena。 6位客人的每一位都要和其配偶之外的每位客人比賽。若沒有人在同一天進行 2場比賽，則要在最少天數(shù)完成比賽，如何安排？ 解：用點表示參賽人，兩點連線當且僅當兩人有比賽。 問題對應于求狀態(tài)圖的一種最優(yōu)邊著色 (用最少色數(shù)進行正常邊著色 )。而 Δ=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 課程安排問題：某大學數(shù)學系要為這個夏季安排課程表?，F(xiàn)有 10名學生 (如下所示 )需要選修這些課程。 (學生用 Ai表示） A1: LA, S 。 A3: MA, G, LA。 A5: AC, LA, S 。 A7: GT, MA, LA 。 A9: AC, S, LA。 解：把課程模型為圖 G的頂點，兩頂點連線當且僅當有某個學生同時選了這兩門課程。 (1) 求點色數(shù) 一方面，因圖中含有奇圈 (紅色邊 ), 所以，點色數(shù)至少為 3。在此路口處安置了交通燈。為了 (最終 )讓所有的車輛的燈都能夠安全通過路口，對于交通燈來說，所需要的相位的最小數(shù)是多少？ L5 L4 L3 L2 L1 L9 L8 L7 L6 44 1 0 x t 0 1 2 ?1 ? 0 1 n 解：車道模型為頂點，兩點連線當且僅當兩個車道上的車不能同時安全地進入路口。一方面， 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)了正常點著色。 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è) 請舉例說明最短路算法應用、最小生成樹應用、偶圖匹配應用、平面圖應用、邊著色應用、點著色應用。 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
教學課件相關推薦
鄂ICP備17016276號-1