目 录
摘要 1前言 2
1 问题提出 3
2 问题和符号假设 4
2.1 问题假设 4
2.1 符号假设 4
3 相关定义和定理 5
3.1 网络最大流问题 5
3.1.1 网络与流 53.1.3 增广链 7
3.1.4 截集与截量 8
3.2 寻求最大流的标号法 10
3.2.1 算法思想 10
3.2.2 算法步骤 10
4 问题分析与解决 12
4.1 单个公司招聘情况 12
4.2 多个公司招聘情况 20 4.2.2 对专业集合与公司集合进行分析 22
结论 25
参考文献
26致谢 27
附录 28附2 公司招聘的网络图I的最大流求解 29
附3 最大流Delphi程序 30
摘 要
本文将专业招聘问题转化为图论中的网络最大流问题，并建立网络模型，用网络图（2分图）表示招聘的关系，利用Fold－Fulkerson标号算法求出该网络图的最大流，据此，可求出是否存在满足公司招聘条件的方法。该算法的时间复杂度为O(m*n*U) ，其中m为弧的数目,n点的数目,U为弧上容量的最大上界。先考虑单个公司招聘不同专业的毕业生若干名的情况，然后推广到多家公司的招聘情况。首先，我们建立表示公司和毕业生关系的网络图，虚设1个发点和1个收点。从发点到每个毕业生点的弧的流量皆为1，从毕业生点到公司点的弧的流量皆为1，从公司点到收点的弧的流量根据公司招聘毕业生的人数确定。利用Fold－Fulkerson标号算法求得其最大流和相应路径。然后，建立专业与公司关系的网络图，同样利用标号算法求解。
本文在解决公司招聘问题中建立的两种网络图都可以求解出最大流，但是后者在时间效率上明显优于前者，因此我们在建立网络模型解决问题时要充分考虑到网络图中顶点的数目与边的数目的关系，实现两者的平衡，达到最优的效果。
关键词：网络方法；最大流；Fold－Fulkerson标号算法；专业招聘模型
Abstract
This paper transforms the specialized employment advertise question into the maximal-flow problem in the network of the graph theory , and establishes the network model . Then , extracts the maximal-flow of this network chart which is used to express the relationship of the specialized employment advertise question by using the Fold-Fulkerson marking algorithm . According above , we can extract whether exists satisfies of the requirements the method of the company . This algorithm complexity time is O(m*n*U), in which m is the arc number , n is the point number , U is the biggest upper boundary of the arc the capacity . Considered the single company advertises for different specialized graduate situations first . Then promotes to many companys employment advertise situation . First , establish the network chart expressed the relations between the company and the graduate and create an nominal spot of sends and receives . The capacity of arc from sends to each graduate is 1 , the arc current capacity from the graduates to the company all is 1, the arc current capacity from company to receives are determined by the requires of graduates . Obtains its maximal-flow and the corresponding way using the Fold-Fulkerson marking algorithm . Then, establishes the network chart which relate the specialty and the company . In the same , using marking algorithm to solve the problem .
The two network charts established in this paper are to be possible to solve the maximal-flow of the specialized employment advertise question . The latter surpasses the former obviously in the efficiency of the time . Therefore , must consider fully in the relations of the apex number and the side number when establishes the network model to achieve the balance and the most superior efficient .
Key words: Network method; Maximal-flow; Fold-Fulkerson marking algorithm; Specialized employment advertise model.
前言
图与网络分析（Graph Theory and Network Analysis），是近几10年来运筹学领域中发展迅速、而且10分灵活的1个分支。由于它对实际问题的描述，具有直观性，故广泛应用与物理学、化学、信息论、控制论、计算机科学、社会科学、以及现代经济管理科学等许多科学领域。
网络最大流问题和它的对偶问题——最小截问题，是1对经典组合优化问题，它们在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容。最大流问题已经有40多年的研究历史，近年来，随着各种网络的飞速发展，最大流问题的研究也取得了很大的进展。对最大流问题研究做了详细的总结，并对下1步研究趋势进行了预测。
网络流算法是1种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中的其它1些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决1些搜索与动态规划无法解决的非np问题。
网络流在具体问题中的应用，最具挑战性的部分是模型的构造，它没用现成的模式可以套用，需要我们对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），根据具体的问题发挥我们的创造性。1道问题经常可以建立多种模型（网络图），不同的模型对问题的解决效率的影响也是不同的，本文通过实例探讨如何确定适当的模型，提高网络流算法的效率。本文中建立的网络图可有多种，笔者分别以毕业生集合与公司集合和专业集合与公司集合建立网络模型图，通过Ford Fulkerson标号算法解决最大流，并分析解两种网络图最大流的时间复杂度。本文在解决公司招聘问题中建立的两种网络图都可以求解出最大流，但是后者在时间效率上明显优于前者，因此在建立网络模型解决问题时要充分考虑到网络图中顶点的数目与边的数目的关系，实现两者的平衡，达到最优的效果。