论文部分内容阅读
【摘要】图论〔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
图论参与管理方面的研究有着广阔的天地。饱和安排双边会议组合问题，就是在一个复杂的关系网中，
需要梳理出各种双边关系，从而进行饱和会场安排。比如参加一个系统工程小组讨论会，各小组间需要
单独讨论，形成会议结果。在同一时间段最大安排的会议数，就是饱和性问题。研究这类问题涉及的领
域广泛，具有极其高的应用价值。本文应用图论知识，通过例子具体说明和探讨如何实现饱和安排双边
会议组合问题，进行算法研究。
【关键词】图论二维表格饱和安排算法研究
1.问题的提出
图论极有趣味性和实用性，从逻辑上来讲它是组合数学的一个重要分支。虽然图论表面上研究点和线的
学问，但其理论的应用领域十分广阔，已经超出了数学和计算机应用学科。还涵盖了社会学、交通管理
、电信领域，管理研究等。图论所研究的内容也非常广泛。例如图的连通性、遍历性、图的计数、图的
着色、图的极值问题、图的可平面性等。探讨图论中的饱和安排双边会议组合问题，就是要利用图论解
决生活中的现实问题。
比如ABCDEFG分别代表一个专业小组，要进行交叉讨论技术问题，而每一个小组的作用和地位不同，有些
小组和其他小组的关系比较复杂，比如下图：
图1
图中的边代表两小组需要技术会议，如果全部会议需要规定的时间内完成，每一个时间段每一个小组只
能安排一次会议，比如AC会议。这就需要能解决饱和安排的算法来完成。具体说来有以下几个方面的考
虑：
1.边的两头一起参加会议，而且只能一次。比如AC会议结束后，不再安排AC会议了。
2.边的两头在同一时间段只能出现一次。比如上午开了AC，BD，上午就不能出现AD。
3.能得出最短时间完成全部会议，也就是饱和状态的算法研究。
2.算法的研究
单从图1很难找出内在的逻辑联系和同步异步的关系，我们可以把图1转换为二维表格形式。一个简单图
G=
结点的编序有密切关系：
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