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

　　【摘要】图论〔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 integer
　　For i=1 to N
　　A(1 to n)=行统计/2…………….因为对称
　　M(1 to n)=列统计/2…………….因为对称
　　NEXT i
　　For i=时间一 to 时间 M…………….N行
　　While M（i）+A（w）最大 and (没有标记颜色)
　　安排 Y（i，w）
　　i行和w行，i列和w列标记颜色不能再安排
　　until 全部标记颜色了 or 没有大于0的单元格了
　　next i
　　if 整个表没有大于0的单元格了
　　提示允许这样安排
　　结束
　　否则，提示"现有会议数数已经到达或超过了最饱和状态（临界状态），这次安排不合理也不允许。"
　　3.总结
　　通过编程实现了饱和安排会场的问题，但在编程中通过改变数据控件的颜色区别是否能再选择安排，需
　　要对数据控件编程有所掌握。
　　图论算法和理论十分独特精妙，图论模型的建立和优化十分灵活。因此，对图论模型的研究需要一定的
　　数据结构基础和实践性很强的研究，需要耐心和坚持。从上面的例子我们可以看出，图论的应用十分广
　　泛，如果我们在学习的过程中能打下坚实的基础，就有能力将图论的思想应用到纷乱复杂的现实问题中
　　去。
　　参考文献
　　［1］ 舒贤林，徐志才．图论基础及其应用［M］．北京：北京邮电学院出版社．1988．
　　［2］张先迪，李正良．图论及其应用［M］．北京：高等教育出版社．2005．
　　［3］孙惠泉．图论及其应用［M]．北京：科学出版社，2004：1-2