If $G$ is a bipartite graph, Hall's theorem \cite{H35} gives a condition for the existence of a matching of $G$ covering one side of the bipartition. This theorem admits a well-known algorithmic proof involving the repeated search of augmenting paths. We present here an alternative algorithm, using a game-theoretic formulation of the problem. We also show how to extend this formulation to the setting of balanced hypergraphs.
翻译:如果$G$是一个双部分图, Hall 的定理 \ cite{H35} 提供了存在一个匹配值的条件, 匹配值为$G$, 覆盖两部分的一面。 这个定理承认了一个众所周知的算法证据, 涉及反复搜索增量路径。 我们在此提出一个替代算法, 使用对问题的游戏理论配方。 我们还展示了如何将这个配方扩展至平衡的超直线设置 。