1.2 圖的獨立集應用

問題描述 各大學教務處每學期臨近結束時，都需要根據各任課老師任課計劃和學生選課情況，再結合教室資源情況安排下一學期的課程及上課時間和地點.表1.2所示是某大學電信學院的大三各專業部分課程情況.該學院每屆學生按專業分班，統一選課.另外，學院只有一間普通機房和一間高級機房.那么應該如何合理地安排這些課程呢?

思路分析 一般來說，在大學里，每學期任課老師都有一定工作量的要求，往往可能要上不止一門課程，或同一門課程有多個教學班，而每位同學需要在學期內完成若干門課程的學習（但受專業限制，同專業所選課程差異較小），因此我們在安排上課時間時一定要保證同一位老師教授的任意兩門課程和同一專業的學生學習的任意兩門課程不可排在同一時間.另外，對于某些對上課設施有特殊要求的課程，也不可以安排在同一時間，因為特殊設施資源是非常有限的，比如機房、球場等.由于受到教室數量的限制，在同一時段無法安排數量超過教室數量的課程.另外，為了方便開展一些全校性的活動，我們希望有些時段可以不安排課程，所以在安排課程時希望上課的時段盡量少.

模型建立 基于這一要求，我們可以構造圖1.13所示的示意圖.以每個課程為頂點，兩個頂點連一條邊，當且僅當兩門課程的任課老師為同一人，或有學生同時選了這兩門課，或上課教室沖突.那么一個合理的課程安排就是將圖中的點進行分化，使得每一個部分里的點都兩兩不相連.我們把這一劃分的過程可以看成是對圖的頂點著色，使得相連的兩個頂點顏色不一樣，這樣每一個色部里的點都是兩兩不相連的，也就是一個獨立集.這樣每一色部里的點所代表的課程就可以安排在同一個時間段了.在本例中，我們用字母a,b,c,d,e,f,g按序表示上述7門課，得到圖1.13.我們尋找劃分的主要方法是通過極小覆蓋找出圖中的極大獨立集，然后刪去該極大獨立集，在剩下的圖中找出極大獨立集，直到剩下的圖為一個獨立集.這樣，每次得到的獨立集就可以作為劃分的一部分.由于教室數量有限，如果得到的獨立集較大，則可以再進一步劃分，以便不超過教室的數量上限.

在本例中，我們可以用代數方法找出一個劃分.圖1.13中的點表示課程，兩點之間的連線則說明這兩門課程沖突，不能安排在同一時段.

模型求解 為了得到極小覆蓋，對于任意頂點v，選擇v或者選擇所有鄰點.為了有效地執行這個程序，我們利用代數方法.首先把選擇頂點v這個指令簡記為符號v，隨后對給定的指令X和Y，指令“X或Y”和“X與Y”分別記為X+Y（邏輯和）和XY（邏輯積）.例如，指令“選擇u與v，或者選擇v與w”記為uv+vw.根據邏輯運算規則，我們可以得到

（uv+vw）（u+vx）=uvu+uvvx+vwu+vwvx.

現在考察本例中的圖，我們的指令用于求極小覆蓋時就是

（a+bd）（b+aceg）（c+bdef）（d+aceg）（e+bcdf）（f+ceg）（g+bdf），

上式可化簡為

aceg+bcegd+bdef+bcdf，

換言之，選擇a、c、e與g，或者b、c、d、e與g，或者b、d、e與f，或者b、c、d與f.因此{a,c,e,g},{b,c,d,e,g},{b,d,e,f}和{b,c,d,f}是G的極小覆蓋.取其補集，得到G的所有極大獨立集{b,d,f},{a,f},{a,c,g}和{a,e,g}.我們可以任選一個極大獨立集作為劃分的第1部分，再用同樣的方法求去掉該獨立集的圖中的極大獨立集，選取某一個作為劃分的第2部分，這樣進行下去，我們就得到一個完整的劃分（{b,d,f},{a,e,g},{c}）.在這樣的劃分下，這些課可以分為3個時段，第1時段的3門課程b,d,f，第2時段的3門課程a,e,g和第3時段的1門課程c.

注意，本模型中所用的求劃分的辦法本質上來講是一種枚舉法，在求極小覆蓋的過程中用的邏輯運算方法的效率受到圖的頂點數目的影響，因此本方法只適用于頂點數較少的圖.對于頂點數目較多的圖，尚無高效的劃分數最少的劃分方法.