# Not able to understand the skew symmetry property in Flow Network

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?

• 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.
– avs
Commented May 3, 2019 at 22:04
• @avs That doesn't seem like you're talking about network flows; electric circuits follow somewhat different conventions. Commented May 3, 2019 at 22:09
• In a circuit with constant current, how is it not flow?
– avs
Commented May 4, 2019 at 1:44

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$$.
• 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? Commented May 3, 2019 at 22:17
• Sorry, typo. $u$ should be $w$. I fixed it now. Commented May 3, 2019 at 22:20
• So basically its easier to represent net flow, thats why we use skew symmetry? Commented May 3, 2019 at 22:51
• Right. Well, there's probably a number of things that become easier or harder to represent, but that's one of them. Commented May 3, 2019 at 22:56