Some flow related question

Revision en1, by 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).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English drastogi21 2020-06-05 21:09:14 564 Initial revision (published)