大型科技會(huì)議議程安排問(wèn)題(編輯修改稿)
2025-04-21 12:50 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的，因?yàn)椴徽撈渲卸嗌偃?，每個(gè)人至少有一項(xiàng)彼此不同的工作。充分性：若對(duì)于任何，恒有 ，則可以按下面的方法作出匹配M,使得X關(guān)于M飽和。先作任一初始匹配，若已使X飽和，則定理已證。如若不然，則X中至少有一點(diǎn)x0非飽和，則從x0出發(fā)，檢查從x0開始，終點(diǎn)在Y的交互道，可能有一下兩種情況發(fā)生：（1） 沒(méi)有任何一條交互道，可以達(dá)到Y(jié)的非飽和點(diǎn)，這時(shí)由于從x0開始的一切交互道，終點(diǎn)還是在X，故對(duì)于X的子集A有 。這與假設(shè)矛盾，所以這種情況是不可能的。（2） 存在一條從x0出發(fā)的交互道，終點(diǎn)為Y的非飽和點(diǎn)，則這條道路便是可增廣道路，因而可以改變一下匹配使x0點(diǎn)飽和。重復(fù)以上的過(guò)程，就可以得到匹配M，使得X全部飽和，定理的充分性得證。上面得證明給出了一個(gè)求最大匹配得算法，這個(gè)算法習(xí)慣上被稱為匈牙利算法。定理三 設(shè)G是2部分圖且p≥Δ,則G中存在p個(gè)不交匹配M1,M2,...,Mp,使得 并對(duì)每個(gè)均有(ε表示圖的邊數(shù)) 證明參見(jiàn)③，第311頁(yè)。（三）色數(shù)問(wèn)題已知圖G＝(V,E),其中|V|=n,|E|=m,對(duì)圖G的所有頂點(diǎn)進(jìn)行著色時(shí)，要求相鄰的兩頂點(diǎn)的著色不一樣，問(wèn)至少要多少種顏色？這就是頂點(diǎn)的著色問(wèn)題。對(duì)圖G＝(V,E)的頂點(diǎn)進(jìn)行著色的結(jié)果就是把頂點(diǎn)集V劃分成若干個(gè)不相交的子集，而且每一子集中的任意兩點(diǎn)都不相鄰，這樣的集合叫做獨(dú)立集。設(shè)圖G的某一頂點(diǎn)集合是獨(dú)立集，但是任意增加一點(diǎn)就破壞它的獨(dú)立性，則稱這個(gè)獨(dú)立集是極大的獨(dú)立集。圖中頂點(diǎn)個(gè)數(shù)最多的極大獨(dú)立集叫最大獨(dú)立集，它的的頂點(diǎn)數(shù)叫做圖的獨(dú)立數(shù)。引理一 獨(dú)立集問(wèn)題是NP完全的。所謂獨(dú)立集問(wèn)題就是：任給一個(gè)無(wú)向圖G＝(V,E)和非負(fù)整數(shù) J≤|V|,問(wèn)G是否有大小不小于J的獨(dú)立集？這個(gè)問(wèn)題是一個(gè)典型的NP完全問(wèn)題。證明可以參見(jiàn)⑤，第243－246頁(yè)。由這個(gè)引理很容易得到下面的結(jié)果。命題二 頂點(diǎn)著色問(wèn)題是NP完全的。三、理論分析（一）議程安排的參數(shù)確定時(shí)間片個(gè)數(shù)k的確定 k0是理論上能使議程安排成功的最少時(shí)間片數(shù)，在沒(méi)有有序沖突，并且足夠會(huì)場(chǎng)的條件下，k0就是場(chǎng)次及其沖突關(guān)系形成的圖點(diǎn)著色的色數(shù)。在一般情況下，k0是比較難確定的。在實(shí)際操作中k一般按慣例來(lái)取。會(huì)場(chǎng)的個(gè)數(shù)m （二）問(wèn)題的復(fù)雜性分析議程安排問(wèn)題可以近似地看成兩個(gè)問(wèn)題的組合。會(huì)議場(chǎng)次的時(shí)間安排，使之兩兩之間不沖突，并滿足預(yù)定義的順序。給每個(gè)時(shí)間段內(nèi)的場(chǎng)次安排會(huì)場(chǎng)。先看第二個(gè)問(wèn)題，用點(diǎn)表示場(chǎng)次和會(huì)場(chǎng)，用點(diǎn)和點(diǎn)之間的連線表示場(chǎng)次和會(huì)場(chǎng)之間的可用關(guān)系。這樣就形成一個(gè)2部分圖。會(huì)場(chǎng)安排時(shí)間上就是求這個(gè)2部分圖的最大匹配。這可以用匈牙利算法求解。對(duì)于圖G=(V,E),|V|=n,|E|=m，算法的復(fù)雜度是O(mn)。目前最好的算法的復(fù)雜度是O(mn1/2)。參見(jiàn)④，第268頁(yè)。再看第一個(gè)問(wèn)題。第一個(gè)問(wèn)題是一個(gè)比較困難的問(wèn)題，目前尚未見(jiàn)到精確而快速的算法。即使不考慮有序沖突的限制，解起來(lái)也是困難的。在沖突全都是無(wú)序沖突的時(shí)候，第一個(gè)問(wèn)題實(shí)際上可以化成一個(gè)圖的點(diǎn)著色問(wèn)題。對(duì)這個(gè)問(wèn)題的求解只能采取近似算法，比如鮑威爾法。為了得到理想的結(jié)果只能對(duì)沖突關(guān)系集合作一些特殊限定。當(dāng)考慮到順序關(guān)系時(shí)，問(wèn)題就更復(fù)雜了。在這種情況下，當(dāng)將不沖突的兩個(gè)場(chǎng)次安排在同一時(shí)間進(jìn)行時(shí)，可能使其它的原本不沖突的場(chǎng)次變得沖突了。比如，有4四個(gè)場(chǎng)次，它們之間的沖突關(guān)系如圖所示，（1，3），（2，4）都是不沖突的，但是當(dāng)把1，3安排在同一時(shí)間進(jìn)行時(shí)，2，4就有沖突了。而無(wú)序沖突就沒(méi)有這個(gè)問(wèn)題。 1 4
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1