algorithm - 二分匹配的贪心算法

Question

所以我遇到了一个问题，其中有“n”位飞行员和“m”架飞机。每个飞行员都有一份他可以驾驶的飞机的 list 。一名飞行员一次只能驾驶一架飞机。您必须确定可以同时飞行的最大飞机数量。标准的二分匹配问题(我后来才知道)。

在比赛中，我想出了一个贪心算法如下:

While there are planes in the graph :

1)Select a plane which can be flown by minimum number of pilots

2)Greedily allocate a pilot to that plane (from the ones who can fly it)

3)Remove both the plane and the allocated pilot from the graph

一般来说，对于二分匹配问题，我提出如下算法:

While there are nodes in the right set of the bipartite graph :

1)Select a node from the right set with minimum incoming degree

2)Greedily match it with ANY node from the left set (which has an edge to it)

3)Remove both these nodes from the graph( this would also involve decreasing the incoming degree of all nodes on the right to which this node has an edge to)

我在数学上并不精通，无法证明该算法的正确性，经过大量思考后，我无法想出一个反例。所以我的具体问题是，这是标准算法还是已知算法，还是我犯了一些我看不到的明显错误？

如果您愿意，请随时编辑我的问题以使其更清楚。谢谢。

Answer 1

反例:

   a1  a2  a3  a4  a5
p1  x   x
p2  x   x   x   x         
p3  x   x   x   x   
p4                  x
p5          x   x   x

首先选择 a5。随机选择可能是 p5 的飞行员。如果是，则 p4 没有平面。