algorithm - 从每条边中选择一个顶点

Question

这是一个很容易解释的问题，但我在找出解决方案时遇到了一些困难。我最喜欢的那种!

让 G=(V,E) 成为一个二部图。我需要计算最小子集 V'，以便对于每条边 e=(u,v)，u 属于 V' 或 v 属于 V'。如果有不止一种解决方案，任何人都可以接受。

|V| <= 2000

|E| <= 10000

任何提示都可能有用:D

Answer 1

Konig's theorem是相关的。