algorithmgraphdirected-graphbipartitenetwork-flow

Bipartite matching to flow network

I have a directed graph, with category A that is able to kill category B.

I'm able to transform it into a flow network but my issue is, if i have some nodes without any arrows, like a lonely node, do I connect it to the source and sink or I remove it from my network flow ?

Thanks

Solution

  • If you're trying to find a bipartite matching using a max flow algorithm, either works, since either way there's no path from source to sink through the isolated node, therefore it does not affect the flow calculation.