大型科技會議議程安排問題-wenkub
2023-04-09 12:50:23 本頁面
【正文】 者叫做有序沖突或有序沖突。定義兩個場次固有沖突，如果兩個場次屬于相同的分組或者兩個場次有相同的主持人或發(fā)言人。（二） 問題的數(shù)學(xué)描述 原始問題議程安排考慮的主要對象是：場次、時間片和會場。如何將這些報告安排在9天的時間內(nèi)，使它們互不沖突，這就是議程安排問題。AbstractWith graph theory, this article analysis the scheduling of normal academic conferences, and give an algorithm of schedule planning. The main examples of this article are the two International Conference of Mathematics just held in Berlin 1998 and will hold in Beijing 2002. A puter program was made according to the algorithm. It can give the scheduling of kinds of largescale academic conferences.一、議程安排問題的數(shù)學(xué)描述（一） 問題的提出在各種國際學(xué)術(shù)交流中，召開學(xué)術(shù)會議是最直接的了。大型科技會議議程安排問題The Scheduling of Large Academic Conference北京大學(xué)數(shù)學(xué)學(xué)院98級 于海軍摘要本文利用圖論作為工具討論了一般科技會議的議程安排問題，給出了議程確定的一些準(zhǔn)則，并對不同的情況給出了用計算機(jī)進(jìn)行自動安排議程的算法。目前的國際學(xué)術(shù)會議種類有很多，規(guī)模也在逐漸變大。需要指出的是，科技會議議程安排問題之所以能成為一個數(shù)學(xué)問題是因為這種會議除了大會形式之外還有分組會議，存在大量的并行進(jìn)行的場次。場次由會議的程序委員會確定，時間片由組委會根據(jù)慣例或者當(dāng)?shù)氐淖飨⑶闆r確定，會場是組委會根據(jù)對會議的人數(shù)、場次等項的估算而安排給會議使用的會場。如果兩個場次有固有沖突，則它們不能安排在同一個時間片內(nèi)。議程安排問題就是在場次、會場、時間給定的情況下， 為每個場次指定一個時間片，一個會場，并且使得有a、 有沖突的場次不在相同的時間片內(nèi)，對于有序沖突，場次要滿足序的限制。場次作為端點，沖突關(guān)系作為邊。 數(shù)學(xué)表述給定場次集合為 ，會場集合為 ，時間片數(shù)為k,無序沖突矩陣,有序沖突矩陣,場次會場可用關(guān)系矩陣 ,議程安排問題就是求S的一個劃分,以及場次到會場之間的一個映射r，滿足以下條件：（1）（2）設(shè) 若若（3）設(shè) 若（4）若二、相關(guān)預(yù)備知識（一）圖論基本概念我們用G=(V,E)表示一個圖，V表示圖的頂點集合，E表示點和點之間的連線的集合，這些連線稱為邊。頂點度為零的點稱為孤立點。W中邊的數(shù)目k稱為W的長度。對圖G中的任意兩個端點x,y,若G中存在連接x和y的路，則稱x和y是連通的。G中與M中邊關(guān)聯(lián)的頂點稱為M飽和點。設(shè)M是二部圖G=(V,E)的一個匹配。對稱差：A,B是兩個集合，定義 定理一 M為最大匹配的充要條件是不存在可增廣道路。先作任一初始匹配，若已使X飽和，則定理已證。重復(fù)以上的過程，就可以得到匹配M，使得X全部飽和，定理的充分性得證。對圖G＝(V,E)的頂點進(jìn)行著色的結(jié)果就是把頂點集V劃分成若干個不相交的子集，而且每一子集中的任意兩點都不相鄰，這樣的集合叫做獨(dú)立集。所謂獨(dú)立集問題就是：任給一個無向圖G＝(V,E)和非負(fù)整數(shù) J≤|V|,問G
法律信息相關(guān)推薦
鄂ICP備17016276號-1