匈牙利法中直线覆盖选择的最小值

对二部图最小点覆盖的理解:求最少的点数使得二部图的所有边在这些点中至少有一个端点。另一方面，通过删除包含这些点的边，可以删除所有的边。

最小点覆盖:选择最少数量的点，以便选择任意边的至少一个端点。最大独立数:选择最多的点，使任意选定的两点不相连。

最小路径覆盖:对于DAG(有向无环图)，选择最少数量的路径，使得每个顶点属于且仅属于一条路径。路径长度可以是0(即单点)。

匈牙利

匈牙利算法是一种利用增广路径寻找二部图最大匹配的算法，其核心是寻找增广路径。匈牙利算法是一种解决P问题(多项式时间)中任务分配问题的组合优化算法。它促进了后来的原始对偶法。

匈牙利算法是由美国数学家哈罗德·库恩在1955年提出的。这个算法被称为匈牙利算法是因为它的很大一部分是基于前匈牙利数学家Dénes K？黑鬼和珍？基于埃格尔瓦里的工作。