什么是匈牙利算法？Hall定理是什么？
谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：│T(A)│>=│A│ 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束，否则进行第3步；
3．在X中找到一个非饱和顶点x0，作V1←{x0},V2←Φ； 4．若T(V1)=V2则因为无法匹配而停止，否则任选一点y∈T(V1)V2； 5．若y已饱和则转6，否则做一条从x0→y的可增广道路P，M←M?E(P)，转2；
6．由于y已饱和，所以M中有一条边(y,z)，作V1←V1∪{z},V2←V2∪{y}，转4； 设数组up[1..n]—标记二分图的上半部分的点。 down[1..n]—标记二分图的下半部分的点。 map[1..n，1..n]—表示二分图的上，下部分的点的关系。 True-相连，false—不相连。 over1[1..n]，over2[1..n]标记上下部分的已盖点。 use[1..n，1..n]-表示该条边是否被覆盖。 首先对读入数据进行处理，对于一条边(x，y)，起点进集合up，终点进集合down。标记map中对应元素为true。 1.寻找up中一个未盖点。 2.从该未盖点出发，搜索一条可行的路线，即由细边出发，由细边结束，且细粗交错的路线。 3.若找到，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。 4.统计use中已覆盖的边的条数total，总数n减去total即为问题的解。
延伸阅读
匈牙利算法得出的最优解唯一吗？
不惟一。扩张的顺序不同,枚举顶点的顺序不同,解就不一定相同
hall定理例题？
Hall定理是二分图匹配问题中匈牙利算法的基础。
中文名
Hall定理
适用领域范围
X中的任意k个点至少与Y中的k个点相邻
适用领域范围
二分图匹配问题
推导结论
匈牙利算法
Hall定理：
此定理使用于组合问题中，二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,………,Xm}, Y={y1, y2, y3, y4 ,………,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：
X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)
本论还有一个重要推论：
二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t—正则的二部图存在完美匹配。
匈牙利法的由来？
答：匈牙利算法，是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。
匈牙利算法得到的结果是稳定的吗？
不是。匈牙利算法得到的结果根据实验条件的变化而产生波动。
一道MBA考试题(《数据、模型与决策》)？
这个题属于指派问题，可以用“匈牙利算法”，大学里面《运筹学》会学，最终答案是：甲完成A,乙完成E,丙完成B，丁完成C，戊完成D。最少时间为：18。具体算法过程需要用矩阵的形式，阐述比较麻烦，你最好看看《运筹学》的指派问题那一章。看懂了很简单的！
匈牙利算法的优缺点？
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法。
匈牙利算法是一种组合优化算法，它是解决多项式时间复杂度问题的较快方法。
1.从每一行中找到最小元素，然后从该行的所有元素中减去该值；
2.从每列中找到最小元素，然后从该列中所有元素中减去该值；
3.令m =覆盖表中所有零所需的最小行数；
4. while（m！=覆盖表中所有零所需的最小列数）
从发现的元素中找到最小的元素
从所有其他未发现的元素中减去该元素
将此元素添加到线条相交的元素中
寻找新的
5.使用零来分配可能的组合，即：只要存在零，就可以分配任务；
6.找到最低成本；
7.结束。
