圖論數(shù)學(xué)模型

圖論數(shù)學(xué)模型第一頁，共十三頁，編輯于2023年，星期二2.3建立圖模型

解決實際問題的趣例第二頁，共十三頁，編輯于2023年，星期二例1節(jié)目排序問題一場文藝演出共有8個節(jié)目,全體演員中有10人須參加兩個以上的節(jié)目演出,情況如表，表中的√號所示,如演員1要參加三個節(jié)目A、B和H.若節(jié)目主辦單位希望首尾兩個節(jié)目為A和H,或為H和A,并且希望每個演員不連續(xù)參加兩個節(jié)目的演出,試為主辦單位安排一個節(jié)目順序表.

第三頁，共十三頁，編輯于2023年，星期二第四頁，共十三頁，編輯于2023年，星期二分析如演員1要參加三個節(jié)目A、B和H。若節(jié)目主辦單位希望首尾兩個節(jié)目為A和H?；驗镠和A，并且希望每個演員不連續(xù)參加兩個節(jié)目的演出，試為主辦單位安排一個節(jié)目順序表。所謂開頭為節(jié)目A（或H），結(jié)尾為H（或A），可以認(rèn)定是一個圖的出發(fā)點和結(jié)束點，由此考慮，以8個節(jié)目為頂點構(gòu)建圖模型。由于每個演員不連續(xù)參加兩個節(jié)目的演出,意味著對八個頂點聯(lián)線時要注意相鄰頂點的演員關(guān)系.于是決定,若兩個節(jié)目無同一名演員參加,則可連一條邊,表示這兩個節(jié)目可以緊排,否則不連邊,便構(gòu)成一個圖模型（圖2—19）.第五頁，共十三頁，編輯于2023年，星期二解：第六頁，共十三頁，編輯于2023年，星期二例2藥品存儲問題有八種化學(xué)藥品A、B、C、D、P、R、S和T要放進貯藏室保管,出于安全原因,下列各組藥品不能貯在同一室內(nèi):A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D，試為這八種藥品設(shè)計一個使用房間數(shù)最少的貯藏方案。第七頁，共十三頁，編輯于2023年，星期二解：TCP;ABS;RD

第八頁，共十三頁，編輯于2023年，星期二例3工程流程圖（第五屆北京高中數(shù)學(xué)知識應(yīng)用競賽題）機床的大修有如下的工作項目：拆卸③，清洗④，電器檢修④，部件檢查①，零件加工④，零件修理⑤，床身和工作臺研合②，部件組裝（不含電器）②，變速器組裝①，試車③.

1.畫出工序的流程圖，即用圖表示出各項工作的銜接關(guān)系.

2.假定大修期間沒有耽誤任何時間，并把開始拆卸時刻記為0，試問：大修完成的時刻最早是多少？

3.在不影響最短時間完工的條件下，每個工作項目最早和最遲開工時間各是多少？第九頁，共十三頁，編輯于2023年，星期二關(guān)于工序流程圖畫法的說明

（1）“拆卸”，“清洗”等這些具體工作稱為工序，用實箭線“→”來表示。工序名稱寫在箭線上方，完成這項工序的時間寫在箭線下面，箭線的方向代表了工序時間的流向.

（2）工序之間交接處表示的圓圈稱為事項或結(jié)點，用以標(biāo)志前面工序的結(jié)束和允許后面工序的開始，是工序完成或開始的瞬間符號，具有承上啟下、把工序銜接起來的作用.

（3）若A工序必須在B工序完成之后才有條件進行，則稱A是B的緊后工序，或稱B是A的緊前工序.另外，同一對結(jié)點間不能表示兩個及其以上個工序，如圖2－21（左圖）的畫法是不允許的，為此引進了虛工序概念而將此表示式畫成圖2－21（右圖）的形式.第十頁，共十三頁，編輯于2023年，星期二第十一頁，共十三頁，編輯于2023年，星期二解：關(guān)鍵路線為①→②