组合学与图论图论中饱和安排双边会议组合问题

时间：2020-11-20 17:08:57　来源：勤学考试网本文已影响人

第 PAGE 页码页码页 / 总页数 NUMPAGES 总页数总页数页

组合学与图论 [图论中的饱和安排双边会议组合问题]

【摘要】图论〔Graph Theory〕是数学的一个分支，有着相当广泛的应用。随着社会分工的细化，利用图论参与管理方面的研究有着广阔的天地。饱和安排双边会议组合问题，就是在一个复杂的关系网中，需要梳理出各种双边关系，从而进行饱和会场安排。比如参加一个系统工程小组讨论会，各小组间需要单独讨论，形成会议结果。在同一时间段最大安排的会议数，就是饱和性问题。研究这类问题涉及的领域广泛，具有极其高的应用价值。本文应用图论知识，通过例子具体说明和探讨如何实现饱和安排双边会议组合问题，进行算法研究。【关键词】图论二维表格饱和安排算法研究1.问题的提出图论极有趣味性和实用性，从逻辑上来讲它是组合数学的一个重要分支。虽然图论表面上研究点和线的学问，但其理论的应用领域十分广阔，已经超出了数学和计算机应用学科。还涵盖了社会学、交通管理、电信领域，管理研究等。图论所研究的内容也非常广泛。例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。探讨图论中的饱和安排双边会议组合问题，就是要利用图论解决生活中的现实问题。比如ABCDEFG分别代表一个专业小组，要进行交叉讨论技术问题，而每一个小组的作用和地位不同，有些小组和其他小组的关系比较复杂，比如下图：图1图中的边代表两小组需要技术会议，如果全部会议需要规定的时间内完成，每一个时间段每一个小组只能安排一次会议，比如AC会议。这就需要能解决饱和安排的算法来完成。具体说来有以下几个方面的考虑：1.边的两头一起参加会议，而且只能一次。比如AC会议结束后，不再安排AC会议了。2.边的两头在同一时间段只能出现一次。比如上午开了AC，BD，上午就不能出现AD。3.能得出最短时间完成全部会议，也就是饱和状态的算法研究。2.算法的研究单从图1很难找出内在的逻辑联系和同步异步的关系，我们可以把图1转换为二维表格形式。一个简单图G=由V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系：V={v1，v2，…，vn}，V中的结点按下标由小到大编序，则n阶方阵A=(aij)称为图G的邻接矩阵。其中ɑij=表1（二维电子表格）通过转换可以看出已经形成了三角形电子表格，"1"代表有边，空代表没有边。根据上面所说的三个条件，可以得出以下结论：1.一旦选择了其中一条边，节点所在的行和列的任何边都不能再选择，标示为不能选的状态，否则会出现同一时间，同一个小组开两场会议的不合符逻辑的事件。2.随着选择的增多，发展到全部表格都被逻辑标示为不能选择的状态，或者没有边可以选择了。这时候就出现了第一次饱和。如时间一：AC，BD，EG已经饱和。3.当某个时间段饱和时，只能另外一个时间段，整张表格重新标示可选或不可选。根据以上分析，可以用自然语言描述如下：定义N行×N列对称矩阵Y（n，n）表2（数组定义）A(1 to n), M(1 to n)，i，k，w as integerFor i=1 to NA(1 to n)=行统计/2…………….因为对称M(1 to n)=列统计/2…………….因为对称NEXT iFor i=时间一 to 时间 M…………….N行While M（i）+A（w）最大 and (没有标记颜色)安排 Y（i，w）i行和w行，i列和w列标记颜色不能再安排until 全部标记颜色了 or 没有大于0的单元格了next iif 整个表没有大于0的单元格了提示允许这样安排结束否则，提示"现有会议数数已经到达或超过了最饱和状态（临界状态），这次安排不合理也不允许。"3.总结通过编程实现了饱和安排会场的问题，但在编程中通过改变数据控件的颜色区别是否能再选择安排，需要对数据控件编程有所掌握。图论算法和理论十分独特精妙，图论模型的建立和优化十分灵活。因此，对图论模型的研究需要一定的数据结构基础和实践性很强的研究，需要耐心和坚持。从上面的例子我们可以看出，图论的应用十分广泛，如果我们在学习的过程中能打下坚实的基础，就有能力将图论的思想应用到纷乱复杂的现实问题中去。参考文献［1］舒贤林，徐志才．图论基础及其应用［M］．北京：北京邮电学院出版社．1988．［2］张先迪，李正良．图论及其应用［M］．北京：高等教育出版社．2005．［3］孙惠泉．图论及其应用［M]．北京：科学出版社，2004：1-2

相关热词搜索：会议组合图论饱和

组合学与图论图论中饱和安排双边会议组合问题

最新文章

热门文章

组合学与图论 图论中饱和安排双边会议组合问题

最新文章

热门文章

组合学与图论图论中饱和安排双边会议组合问题