数学专业毕业论文.doc

学校代码10812分 类 号O157学 号20080420122吕梁学院毕业论文（设计）国际会议议程安排方案设计系 别数学系专 业数学与应用数学姓 名王李芳指导教师雷 勇职 称助 教日 期2012年6月国内图书分类号：O157 太原师范学院吕梁学院办学点本科毕业论文国际会议议程安排方案设计姓 名王李芳系 别数学系专 业数学与应用数学申请学位学士学位指导教师雷 勇职 称助 教日 期2012年6月摘 要随着社会经济的发展,中外交流日益频繁,目前的国际学术会议种类有很多,规模也在逐渐变大,往往出席人数超过千人,会议场次超过百场,可能分多个专题小组,这就涉及到议程安排问题. 在早期的议程安排过程中,由于场次和会场数都不是很多,一般采用人工安排,这样虽然需要一定量的人力,通常也还在可以接受的范围内.现在传统的人工会议议程安排方式已经不能满足需要,因此自动化的会议议程安排优化问题就应运而生.本文利用图论作为工具讨论了一般科技会议的议程安排问题,给出了议程确定的一些准则,并解决了会议议程安排中两个问题: (1) 同一时间片内的场次与会场的安排; (2) 专题小组参会人员的划分.对于这两个问题给出了其数学理论分析及用计算机进行自动安排议程的算法,实现了简单议程安排程序,方便地解决各种大型会议的议程自动安排问题,最后在C语言程序下实现算法.关键词：会议议程安排;二部图;连通图;最大匹配 ABSTRACTWith the development of society and economic, Chinese and foreign exchange increasingly frequent, there are so species of the current international academic conferences. Also in the increasingly large scale, often attend more than one thousand people, the more than games indefinitely may points more project team. This is involved the agenda. In the early days of the agenda process, because the number of events is not many, generally used the artificial arrangement, while it might need a certain amount of manpower, usually also within acceptable limits. Now the traditional artificial meeting agenda way already can not meet the requirements, so the meeting agenda automatic optimization problem was born. This paper by using graph theory as a tool to discuss the technology of general meeting agenda problem, this paper presents some of the criteria to determine the agenda, and solve the meeting agenda, two problems:(1) The number and the arrangement in the same time;(2) The division of project team of participants.For the two problems this paper gives the mathematical theory analysis and with a computer algorithm of automatic arrangement agenda, an agenda realized simple procedure, convenient to solve various large conference agenda to be automatic arrangement, and finally, in the C programming language algorithm.Key words: Course timetabling; Bipartite graph; Connected graph; Maximal matching目 录引 言1第1章 相关预备知识2 1.1图论的基本概念2 1.2二部图与匹配问题2 1.3图的矩阵表示5第2章 会议议程安排的理论分析及算法设计6 2.1场次与会场安排理论分析6 2.2会议议程安排算法设计7第3 章 专题小组人员划分理论分析及算法设计9 3.1专题小组参会人员划分理论分析9 3.2专题小组人员划分算法设计10结束语12参考文献13谢 辞14附 录15吕梁学院2012届毕业论文(设计)引 言 所谓议程安排(Course Timetabling)问题,顾名思义,就是在一个固定的时间区间内,按照程序委员会的要求,在某些限定条件下,安排一系列会议.在早期的议程安排过程中,由于场次和会场数都不是很多,一般采用人工安排,这样虽然需要一定量的人力,通常也还在可以接受的范围内.但是,随着社会科技的不断发展,中外交流日益频繁,目前的国际学术会议种类有很多,规模也在逐渐变大,往往出席人数超过千人,会议场次超过百场,可能分多个专题小组.以1998年在德国柏林举行的世界数学家大会为例:参加人数超过4000人,分为19个小组,在10天的时间内(包括一个休息日)共安排了大会报告21场,邀请报告164个,口头报告和书面报告1171个.如何将这些报告安排在9天的时间内,使它们互不冲突,这就是议程安排问题,传统的人工方式已经不能满足需要,因此自动化的会议议程安排优化问题就应运而生.但遗憾的是人们很快就证明了会议议程安排(Course Timetabling)问题是NP-完全的优化问题.在过去的三十几年里对自动化课表会议议程安排问题已经有了很多研究成果,但是大部分的研究都是基于时间片互不冲突来进行的,即以会场为单位,对场次进行安排.在此基础上本文将应用所学的图论知识进一步对会场和场次的安排进行优化解决,并设计出专题小组划分最优算法,使其应用与大多数国际会议议程安排,最后在C语言程序下验证算法的精确性及便捷性.第1章 相关预备知识1.1图论的基本概念 用表示一个图,表示图的结点集合,表示点和点之间的连线的集合,这些连线称为边.如果边全是有方向的称为有向图,如果边全都没有方向称为无向图.中元素的个数称为结点数或阶;中元素的个数称为边数.在无向图中,与一个顶点相连的边的数目称为结点的度,记为.顶点度为零的点称为孤立点.用和分别表示的最大和最小结点度.图中连接结点和且长度为k的链,记为链,是指顶点和边交替出现的序列,其中与边相连的两个顶点和正好是的两个端点.和称为的端点,其余的端点成为内部点.中边的数目k称为的长度.边互不相同的链称为迹,内部点互不相同的迹称为路.两端点相同的链(迹、路)称为闭链(迹、路).设是有向图中链(迹、路),指定的方向从到,若中所有边的方向与此方向一致,则称为中从到的有向链(迹、路),记为链(迹、路).对图中的任意两个端点,若中存在连接和的路,则称和是连通的.1.2二部图与匹配问题定义1 设图是图的子图.若对于中任意结点和,如果,有,则由惟一确定,并称是结点集合的诱导子图,记作或;如果无孤立结点,且由所惟一确定,则称是边集的诱导子图,记为或.定义2 给定简单无向图,且, .若和的诱导子图和都是零图,则称是二部图或偶图,并将二部图记作,并称,是的划分.定义3 给定简单无向图,若且中任意两条边都是不相邻的,则子集称为的一个匹配或对集,并把中的边所关联的两个结点称为在下是匹配的.令是的一个匹配,若结点与中的边关联,则称是饱和的,否则,称是不饱和的;若的每个结点都是饱和的,则称是完全匹配.如果中没有匹配,使,则称是最大匹配.显然,每个完全匹配是最大匹配,但反之不真(如图1-1).图1-1中的一个最大匹配为.higfedcba图1-1令是图的一个匹配.若存在一个链,它是分别有和中的边交替构成,则称该链是中的交错链;若交错链的始结点和终结点都是不饱和的,则称该链为增广链;特别地,若交错链的始结点也是它的终结点而形成圈,则称该圈为交错圈.定义4 给定两个集合和,与的对称差,记为,其定义为引理1设和是图中的两个匹配,则在中,每个分图或是交错链，或是交错圈.定理1 图的一个匹配是个最大匹配当且仅当中不含有增广链.证明2 必要性:令是中的最大匹配.用反证法,假设中含有增广链,作其中表示链中所有边的集合.则是的匹配且.可见,不是最大匹配,这与已知矛盾.故中不含增广链.充分性:假设中不含增广链,且不是的最大匹配,于是可令是的最大匹配,则 (1-1)考虑,则由引理可得图 (可见图1-2)中每个分图或是交错连,或是交错圈(它必是偶长度).但因(1-1)知,图中的边比多,所以图中的交错链必以中的边为起始边和终止边,即该链在中是饱和的而在中是不饱和的.因此,该链是中的增广链,这与已知中不含增广链矛盾,于是,必是中的最大匹配.在图1-2(a)中有两个匹配和,其中(b)表示图.(a) (b)图1-2定理2 对于二部图,存在一个匹配,使得的所有顶点关于饱和的充要条件是:对于的一切子集和邻接的点集为,恒有:. 证明3 必要性:若存在一个匹配,使得关于饱和, 是显然的,因为不论其中多少人,每个人至少有一项彼此不同的工作. 充分性:若对于任何,恒有,则可以按下面的方法作出匹配,使得关于饱和.先作任一初始匹配,若已使饱和,则定理已证.如若不然,则中至少有一点非饱和,则从出发,检查从开始,终点在的交互道,可能有一下两种情况发生: (1)没有任何一条交互道,可以达到的非饱和点,这时由于从开始的一切交互道,终点还是在,故对于的子集有.这与假设矛盾,所以这种情况是不可能的. (2)存在一条从出发的交互道,终点为的非饱和点,则这条道路便是可增广道路,因而可以改变一下匹配使点饱和.重复以上的过程,就可以得到匹配,使得全部饱和,定理的充分性得证.上面得证明给出了一个求最大匹配得算法,这个算法习惯上被称为匈牙利算法.1.3图的矩阵表示 给定一个图,使用图形表示法很容易把图的结构展现出来,而且这种表示直观明了.但这只在结点和边(或弧)的数目相当小的情况下才是可行的.显然这限制了图的利用.图的另一种表示法图的矩阵表示法.它不仅克服了图形表示法的不足,而且这种表示可以充分利用现代工具电子计算机,以达研究图的目的. 定义 14 给定简单图,=,中的结点按下标由小到大编序,则阶方阵=称为图的邻接矩阵.其中 . 定义 25 设两个有限集合=,=,则对应于二元关系有一个关系矩阵,其中,这里 ,.例如:=,则.第2章 会议议程安排的理论分析及算法设计2.1场次与会场安排理论分析国际会议议程安排问题之所以能成为一个数学问题是因为这种会议除了大会形式之外还有分组会议,存在大量的并行进行的场次.如果会议没有分组,也就没有同时进行的场次,那么议程安排就是一个简单的排序.议程安排考虑的主要对象是:场次、时间片和会场.场次由会议的程序委员会确定,时间片由组委会根据惯例或者当地的作息情况确定,会场是组委会根据对会议的人数、场次等项的估算而安排给会议使用的会场.场次有以下几个属性: “分组”、“会场大小要求”、“房间媒体要求”、“主持人”、“所有发言人”、“场次类型”;会场有“人数”、“媒体配置”两个属性;时间片有“类型”一个属性,不同类型的时间片有不同的时间长度,对应于不同的场次类型,一般为了安排的方便,各个时间片之间是不重叠的.因此,现在考虑的议程安排问题就是在场次,会场给定的条件下,以及时间片确定的情况下,为每个场次指定一个会场,并且使得会场的大小,媒体配置要符合场次的要求.现在,将场次的房间大小,媒体要求与每一个会场做比较,可以得到每个场次的可用房间列表,可以用一个邻接矩阵 表示,表示第场次可以使用第房间,否则表示不可以使用.有些场次可能有多个会场可以使用.给定场次集合为,会场集合为 ,时间片数为,场次会场可用关系矩阵,议程安排问题就是求的一个划分,以及场次到会场之间的一个映射,满足以下条件6: (1); (2)设 若 (3)若如图2-1,用点表示场次和会场,用点与点之间的连线表示场次和会场的可用关系.由图2-1可知场次1可以使用会场a或会场b,场次2可以使用会场a或d,等等.那么在同一个时间片内不能将场次1和场次2安排在同一个会场a,这就需要合理安排场次到会场的分配.图2-1在图论中称为一个二部图,会场安排实际上就是求二部图的最大匹配,对此我们可以用匈牙利算法进行求解,给出一种合理的求解方法,运用到不同的场合中.会场：场次：edcba4321图 2-1 二部图图2-1场次与会场的关系矩阵可表示为:=.2.2会议议程安排算法设计在同一个时间片内给场次安排会场,首先画出场次和会场之间的可用关系,即以场次和会场为点,场次和会场之间的可用关系为边的二部图,再利用匈牙利算法找出这个二部图的最大匹配,具体算法如下7:(1)在所画的二部图中可以标记出场次的个数为,会场的个数为,场次与会场之间的连线个数为;(2)将场次与会场分别从1开始标号,场次用集合表示,会场用集合表示,并将场次与会场的可用关系的二部图表示成邻接矩阵,表示场次可用会场,表示场次不可用会场; (3)从任一可行顶点标号开始,则然后决定相等子图,并在中选取任意匹配;(4)若是饱和的，则是最大匹配(因为),在这种情形下,算法终止.否则,令u是一个非饱和顶点,置,;(5)若,则转到(6),否则,停止; (6)在中选择一个顶点,考察是否饱和的,若是饱和的,并且,则代替,用代替,则转到(5),否则设是中的可扩路,用代替,并转到(4).算法运行结束, 就是所要找的最大匹配，即会场与场次的分配.算法可为图2-2中的流程图更为直观的描述.在中存在顶点N在可扩路NY开始输入任意的可行顶点标号求 及中的匹配在中是饱和的吗结束 ;N?是饱和的吗YY输出是最大匹配图2-2 求最大匹配流程图第3 章 专题小组人员划分理论分析及算法设计3.1专题小组参会人员划分理论分析由于参会人员来自不同的国家,因此涉及到语言差异问题,为了使来自不同国家的参会人员能够顺利进行交流,就要将参会人员划分多个小组进行讨论,使得在同一个小组内的参会人员有共同语言进行交谈,这就是会议议程安排中专题小组划分问题.给所有参会人员从0开始编号用表示,记参会人数为,则=0,1,2,-1,将参会人员之间语言差异情况表示成图,表示编号为的参会人员,表示编号为的参会人员可以与编号为的参会人员进行交谈(如下例),因此会议议程安排中专题小组划分问题可以转化为找图的连通分图的问题.同时也存在特殊情况,若图本身就是一个连通分图,则参会人员就可以任意划分.例8 举行一个国际会议,有A,B,C,D,E,F,G 7个人.已知下列事实:A会讲英语; B会讲英语和汉语; C会讲英语、意大利语和俄语; D会讲日语和汉语;E会讲德语和意大利语; F会讲法语、日语和俄语; G会讲法语和德语. DGFECBA图3-1 连通图则表示成图为图3-1.图3-1本身就是一个连通图,因此可将A,B,C,D,E,F,G 7个参会人员安排到同一个专题小组下进行讨论.3.2专题小组人员划分算法设计 根据参会人员语言差异情况画出图 (如图3-1),集合中的点表示参会人员,集合中的线表示两两参会人员之间可用同一种语言交流,根据图可以表示出邻接矩阵.(1) ,令为任意顶点集,将;为任意顶点集,将;(2)任意的,将,则令是 的任意一个顶点,在中搜索,如果,则将,;如果不存在,则停止,转到(3);(3)将,输出中所有元素;(4)若,则停止;否则转到(1).具体C语言程序见附录3.算法可为图3-2中的流程图更为直观的描述9-10.N开始, ,并且Y输出集合Q中的所有元素结束?YN 图 3-2 求连通分图流程图结束语本文通过对会议议程安排简单介绍,是人们了解到会议议程安排并不是一件简单的事情,处于对问题的简单化,本文解决了会议议程安排中场次与会场的划分问题以及专题小组参会人员划分问题,使人们对以上两个问题的解决有了一种新的方法,并知道了图论及C语言程序设计的结合在日常生活中的广泛应用,帮助人们解决了很多问题,对于会议议程安排的复杂性分析,由于所学知识有限,本文将不予讨论,希望后来的读者能够继续研究讨论.11吕梁学院2012届毕业论文(设计)参考文献1 F.哈拉里.图论M.上海:上海科学技术出版社,1980:14152 楼世博,金晓龙,李鸿祥.图论及应用M.北京:人民邮电出版社,1982:221226,2392413 徐俊明.图论及其应用M.北京:中国科技技术大学出版社,1998:243254,2662684 卢开澄.图论及其应用M.北京:清华大学出版社,1981:23265 徐俊明.图论及其应用M.北京:中国科学技术大学出版社,1998:2342376 Buckley,FLewinter,MA Friendly Introduction to Graph TheoryM.Beijing:Tsinghua University Press,2005:1451507 谢金星,邢文训.网络优化J.清华大学,2000,23(3):5555588 张立昂.可计算性与计算复杂性导论J.北京大学报,1996,13(5):2362459 王祜民,赵致格.时间表问题中的定额匹配算法J.清华大学学报,1998,24(7):24525210 王祜民.排课表中的分组优化决策算法J.控制与决策,1999,12(3):123126 谢 辞岁月如梭,四年匆匆而过,不知不觉已经走到了最后的路口.相对于四年前迷茫的眼神,现在的我有着更多的坚强与理智,而带给我这些巨大变化的正是我们辛勤耕耘的老师们.回首我四年的求学历程,无一不有着老师们的心血,无论是起步的计算机基础,严谨的高等代数,还是更深一层的数据库、C语言,老师们无一不在用自己的臂膀托起我们明天的希望,他们毫不保留的奉献自己全部的知识与精力,对我们襟怀无私、谆谆教诲、倾心吐露、唯恐不尽.同时,他们也用自己的行动和人格的力量,教会我们做人的道理,指引我们前进的方向.时间总是飞逝而过,现在的我们即将离开老师的庇护,带着老师对我们的殷切希望走向自己的工作岗位,去打拼属于自己的一片天空.但先生之风,定会永远作为我们行动的指南,陪伴激励我们向着更高、更快、更强的目标奋斗. 本论文是在我的指导老师雷勇老师的悉心指导下完成的,雷老师学识渊博,工作严谨,待人诚恳,令我十分敬佩.我从雷老师的身上学到的不仅是专业知识,他的优秀的学习和工作作风、严谨的科学态度以及高尚的品质更使我受益匪浅.作为雷老师带的毕业设计学生,我真的很高兴.在做毕业设计的过程中渐渐和雷老师成为了朋友,使我们的师生情谊更深了一层.我在此由衷地感谢雷老师孜孜不倦的指导、关怀和照顾.此外,我也对同班同学们一并感谢,感谢你们对我的支持和帮助,并让我生活中增加了几个知心朋友.附 录附录1#include #include int n1, n2, m, ans;int result101; /记录V2中的点匹配的点的编号bool state 101; /记录V2中的每个点是否被搜索过bool data101101;/邻接矩阵 true代表有边相连void init() int t1, t2; memset(data, 0, sizeof(data); memset(result, 0, sizeof(result); ans = 0; scanf(%d%d%d, &n1, &n2, &m); for (int i = 1; i = m; i+) scanf(%d%d, &t1, &t2); datat1t2 = true; return;bool find(int a) for (int i = 1; i = n2; i+) if (dataai = 1 & !statei) /如果节点i与a相邻并且未被查找过statei = true; /标记i为已查找过 if (resulti = 0 /如果i未在前一个匹配M中 | find(resulti) /i在匹配M中,但是从与i相邻的节点出发可以有增广路 resulti = a; /记录查找成功记录 return true; /返回查找成功 return false;int main()init(); for (int i = 1; i = n1; i+) memset(state, 0, sizeof(state); /清空上次搜索时的标记 if (find(i) ans+; /从节点i尝试扩展 p