排課表有關(guān)的幾個(gè)問題

1、排課表有關(guān)的幾個(gè)問題2003、2004年間中央民族大學(xué)排課表中午 12 點(diǎn)下課，下午 1 點(diǎn)上課 ,中間休息時(shí)間太短 ,同學(xué)們沒時(shí)間吃飯。出現(xiàn)這些問題 ,是由于 當(dāng)時(shí)學(xué)生擴(kuò)招，而當(dāng)時(shí)文科樓和理科樓均沒有建。如何排課,盡量不出現(xiàn)，或少出現(xiàn)這類問題。這就引出了排課表問題：一所學(xué)校里，有m位教師Xi , X ,，Xm和n個(gè)班級(jí)Yi,Y> ,，Yn ，在明確教師 Xi 需要給班級(jí) Yj 上節(jié)課 pij 之后，要求制定一張課時(shí)盡 可能少的完善的課表，且教室能滿足上課的需求 .這就提出以下幾個(gè) 問題：1、若已知一個(gè)學(xué)校的排課表，判定該排課表是否為最優(yōu)（所排課 時(shí)最少 ,所用教室最少 ）？若不是 ,修

2、改為最優(yōu)的排課表。2、若一所學(xué)校的教師、班級(jí)、教室數(shù)及各班要上的課程均以確定 , 請(qǐng)給出最優(yōu)的排課表 .3、若一所學(xué)校的教師、班級(jí)、教室數(shù)及各班要上的課程均已確定 , 請(qǐng)判定要滿足該校正常教學(xué)， 該校的教室數(shù)是少， 還是多 ?若少， 少多少？若多，多多少？給出具體的精確數(shù)據(jù)。4、若一所學(xué)校有一個(gè)長遠(yuǎn)的發(fā)展規(guī)劃，學(xué)生、專業(yè)數(shù)達(dá)到一定的 規(guī)模，請(qǐng)從最優(yōu)排課的角度，確定學(xué)校所需教室數(shù)量，從而為 學(xué)校發(fā)展規(guī)劃的制定提供理論依據(jù)。定理1圖G是是二部圖（偶圖）當(dāng)且僅當(dāng)G中無奇圈。定理 2 設(shè) E1 , E2 ,., Ek ）是 G 的一個(gè)最優(yōu) k 邊著色 . 若存在 G 中的一 個(gè)頂點(diǎn)u和顏色i及j。使得

3、i不在u上表現(xiàn)，而j在u上至少表現(xiàn)兩次， 則GEj EJ中包含u的那個(gè)分支是奇圈.定理3若圖G是是二部圖（偶圖），則'（G）（G）.定理4設(shè)M和N是G的兩個(gè)不相交對(duì)集，并且|M | |N |，則存在G的 不相交對(duì)集 M '和 N' ，使得 |M '| |M | 1， | N'| | N | 1，且 M ' N' M N. 定理5若圖G （V,E）是是二部圖（偶圖），且p （G），則存在G的p個(gè) 不相交對(duì)集Mi , M2,，M p，使得 E Mi M2 . M p 并且對(duì)于 1 i P ,有/ P I Mj | / p這一理論的幾點(diǎn)應(yīng)用：1

4、、婚姻問題： 一個(gè)鄉(xiāng)村里每位姑娘恰好認(rèn)識(shí)k位小伙子，而每位小 伙子也恰好認(rèn)識(shí) k 位姑娘，那么每位姑娘能和她認(rèn)識(shí)的一個(gè)小伙子結(jié) 婚，并且每個(gè)小伙子也能和他認(rèn)識(shí)的一位姑娘結(jié)婚。定理6若G是k正則二部圖（偶圖）,則G有完美對(duì)集。應(yīng)用 :觸屏手機(jī)、電腦的手寫識(shí)別功能 .2、（ 1）任意 6 個(gè)人在一起 , 其中至少存在 3 個(gè)人或互相認(rèn)識(shí)，或互不相識(shí)。（2）17 個(gè)頂點(diǎn)的完全圖，即 17 邊形, 且每一對(duì)不相鄰的頂點(diǎn)都連以對(duì)角線 所成的圖，用 3 中顏色對(duì)邊任意著色，必存在一個(gè)同色三角形 .（3 ）一所城市的巡警數(shù)量有限 ,分成若干組 , 各組如何巡邏，使得該城市某一 地方一旦發(fā)生突發(fā)事件，不僅立刻

5、有一組巡警到達(dá)現(xiàn)場(chǎng)，而且有其他組 成員盡快趕來支援。（4）費(fèi)馬大定理 : xn yn zn 正整數(shù)解問題。這四個(gè)問題表面上看互不關(guān)聯(lián)，但他們均可建立圖論模型 , 利用圖的著色理論得 到解決。災(zāi)害地區(qū)的郵遞員問題 定理1 G (V,E)是連通非歐拉圖，Eo E,Eo若不是G的邊割，則G中 必存在關(guān)于Eo的可行方案。定理2如果連通非歐拉圖G (V,E)中存在關(guān)于Eo的可行方案，則Eo 中必不包含G中任何奇點(diǎn)的關(guān)聯(lián)邊集。定理3設(shè)e是連通非歐拉圖G (V,E)中任意一條割邊，則G e的兩個(gè) 連通分支中分別都含有G中奇數(shù)個(gè)奇點(diǎn)。定理4如果連通非歐拉圖G (V,E)中存在關(guān)于Eo的可行方案，則Eo 中任何

6、邊都不是G的割邊。定理5在連通非歐拉圖G (V,E)中，邊集E°=Se°,§E是G的一個(gè) S,S邊割，如果G (V,E)中存在關(guān)于Eo的可行方案，則Seo中必含有G 的偶數(shù)個(gè)奇點(diǎn)。給定賦權(quán)非歐拉圖G (V,E,w)，Eo E .Stepl 若w(G Eo) 1，則轉(zhuǎn) Step2;否則，轉(zhuǎn) Step5.Step2若G中存在某個(gè)奇點(diǎn)Vo使E(vo) Eo (定理2),則算法終止。G 上關(guān)于Eo的災(zāi)郵問題無解；否則轉(zhuǎn)Step3.Step3若G的任何邊都屬于G中某個(gè)圈則轉(zhuǎn)Step 4;否則，找出G中 所有不在 任何圈上的邊，記為©,©.，且若E0含有其

7、中某條邊e(1 i l),則算法終止，無解(定理4);否則，轉(zhuǎn)Step4Step4若Eo不是G的S,S邊割則轉(zhuǎn)Step 5;否則，記E。龜,瓦且 若Seo中含有G的偶數(shù)個(gè)奇點(diǎn)(定理5),則轉(zhuǎn)Step 5;否則，算法終止， 無解.Step5把G Eo中每條邊用一對(duì)方向相反的弧代替，各弧上權(quán)值等于對(duì)應(yīng)邊上的權(quán)值，用Floyd算法求出G Eo中任意頂點(diǎn)對(duì)之間的最短路及最短路長，得距離矩陣D （元素dj等于G E。中從m到哲的 最短路長）和路徑矩陣P （元素pj代表G Eo中從y到出的最短路 上與V相鄰頂點(diǎn)的下標(biāo)），當(dāng)頂點(diǎn)Vf與Vg之間不存在任何路徑時(shí)， 令 dfg , Pfg處劃上 。Step6取出G中所有奇點(diǎn)，以這些奇點(diǎn)為頂點(diǎn)構(gòu)成一個(gè)賦權(quán)完全圖Nd M，Ed，Wd），其中各邊上權(quán)值等于相應(yīng)奇點(diǎn)在G Eo中的最短路長。Step7應(yīng)用最小匹配算法求出中Nd的一個(gè)最小匹配M。Step8若M的權(quán)值w（M ） w（m），則算法終止，無解;否則，轉(zhuǎn)m mStep9.Step9對(duì)于M中任意匹配邊mi vs，根據(jù)G E。的路徑矩陣P找出 G E0中從vn到Vs的最短路P （i 1,., k,