Some flow related question

Правка en1, от drastogi21, 2020-06-05 21:09:14

Why is the following true? I cannot understand the intuition behind it.

The weighted maximum independent in a bipartite graph is calculated as follows, connect a dummy source vertex to all left vertices with edge capacity equal to the weights of these nodes in the original graph, do the same with right vertices, and the dummy sink. And for each edge in the original graph, connect the nodes of this edge with infinite capacity in the flow graph. The answer is: (sum of weights of nodes — the maximum flow of this flow graph).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский drastogi21 2020-06-05 21:09:14 564 Initial revision (published)