0
$\begingroup$

From Wikipedia:

$G(V,E)$ is a finite directed graph in which every edge $\ (u,v) \in E$ has a non-negative, real-valued capacity $\ c(u,v)$. A flow network is a real function $\ f:V \times V \rightarrow \mathbb{R}$ with the following three properties for all nodes $\ u$ and $\ v$:

Capacity constraints: ...

Skew symmetry: $\ f(u,v) = - f(v,u)$. The net flow from $\ u$ to $\ v$ must be the opposite of the net flow from $\ v$ to $\ u$.

What exactly is the use of Skew symmetry? I didn't see this property being used anywhere? Basically whats the use of keeping a negative flow from v to u?

$\endgroup$
3
  • $\begingroup$ If a flow is traced along a directed edge, the minus sign says that the direction of the flow is the opposite of that of the edge. See, for example, Kirchhoff's Current Law. $\endgroup$
    – avs
    Commented May 3, 2019 at 22:04
  • $\begingroup$ @avs That doesn't seem like you're talking about network flows; electric circuits follow somewhat different conventions. $\endgroup$ Commented May 3, 2019 at 22:09
  • $\begingroup$ In a circuit with constant current, how is it not flow? $\endgroup$
    – avs
    Commented May 4, 2019 at 1:44

1 Answer 1

1
$\begingroup$

This is not entirely standard - different sources do this differently. If we do use skew-symmetry, then the advantage is that the expression $$\sum_{v \in V} f(v,w)$$ represents the net flow into a vertex $w$: the total flow entering $w$, minus the total flow leaving $w$. This is because (with skew-symmetry) the expression $f(v,w)$ represents both the flow entering $w$ via edge $(v,w)$ and (with a negative sign) the flow leaving $w$ via edge $(w,v)$.

The other approach to representing flows, which I'll define with a function $g$ to distinguish it, is to represent only the flow from $v$ to $w$ by $g(v,w)$, and require $0 \le g(v,w) \le c(v,w)$. In cases where $(v,w)$ and $(w,v)$ are both edges with positive capacity, both $g(v,w)$ and $g(w,v)$ could be positive, independently, though this is redundant. (For example, rather than sending $2$ flow from $v$ to $w$ and $1$ flow from $w$ to $v$, it's equivalent to only send $1$ flow from $v$ to $w$, and $0$ flow from $w$ to $v$.)

Then $g(v,w)$ is simpler to understand (it only represents one thing) but the net flow into a vertex $w$ has a more complicated expression: it is given by $$\sum_{v \in V}g(v,w) - \sum_{v \in V} g(w,v).$$ The first sum represents the flow into $w$, and the second sum represents the flow out of $w$.

We can go back and forth between the two representations:

  • Knowing $g$, we can define $f(v,w) = g(v,w) - g(w,v)$, which will satisfy skew-symmetry.
  • Knowing $f$, we can define $g(v,w) = \max\{0, f(v,w)\}$: when $f(v,w)$ is positive, $g(v,w)$ will represent the same flow from $v$ to $w$, and when $f(v,w)$ is negative, $f(w,v)$ will be positive and $g(w,v) = f(w,v)$ will represent that flow from $w$ to $v$.
$\endgroup$
4
  • $\begingroup$ I didn't understand this line "This is because (with skew-symmetry) the expression $f(v,w)$ represents both the flow entering $u$ via edge $(v,w)$ and (with a negative sign) the flow leaving $w$ via edge $(w,v)$" Where did $u$ come from? $\endgroup$
    – MrRobot9
    Commented May 3, 2019 at 22:17
  • $\begingroup$ Sorry, typo. $u$ should be $w$. I fixed it now. $\endgroup$ Commented May 3, 2019 at 22:20
  • $\begingroup$ So basically its easier to represent net flow, thats why we use skew symmetry? $\endgroup$
    – MrRobot9
    Commented May 3, 2019 at 22:51
  • 1
    $\begingroup$ Right. Well, there's probably a number of things that become easier or harder to represent, but that's one of them. $\endgroup$ Commented May 3, 2019 at 22:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .