1
$\begingroup$

Let there be a bipartite directed graph $G=(V,E)$.

Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean?

How can we extract a flow from a path cover (and similarly, extract a path cover from a flow)?

$\endgroup$
1
$\begingroup$

Presumably, the flow would send $k$ units of flow along the edge $(u,v)$, where $k$ is the number of paths in the path cover that traverse that edge.

I haven't verified that this will always be guaranteed to be a valid flow for all possible path covers, but it doesn't seem like it on first glance, so more context might be needed to resolve that.

$\endgroup$
3
  • $\begingroup$ A flow is feasible if the sum of flow entering all non-source and non-sink nodes is 0. Therefore, I suppose that your flow is feasible as long as all paths start at the source and end at the sink? $\endgroup$
    – shgr1092
    Dec 7 '20 at 12:08
  • $\begingroup$ @shgr1092, that sounds right to me. $\endgroup$
    – D.W.
    Dec 7 '20 at 18:31
  • $\begingroup$ Thank you very much! $\endgroup$
    – shgr1092
    Dec 8 '20 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.