Flows: Graph Theory/Groups, Empty Set

93 Views Asked by At

I am just beginning to understand flows in the context of graph theory. I have found a resource that explains what a flow is but I am confused for the following reason. Assume a commutative group $G$ is given under addition.

Let $\delta^+(v)$ be the set of all edges leaving a single, given vertex $v$ in a given directed graph. If you have no edges leaving the vertex, $\delta^+(v)$ would be the empty set. So, $\sum_{e \in \delta^+(v)}\varphi(e)=\sum_{e \in \varnothing}\varphi(e)$. Can this happen? And if so, would the $\sum_{e \in \varnothing}\varphi(e)=\text{identity element of group G}$, or would it be something else?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes: if there are no edges leaving vertex $v$ so that $\delta^+(v) = \varnothing$, then $$ \sum_{e \in \delta^+(v)} \varphi(e) = 0. $$ (By $0$, I mean the identity element of your commutative group, which I strongly recommend not calling $G$ because you also have a graph that wants to have a name.)

In particular, if you want to satisfy the condition that $$ \sum_{e \in \delta^+(v)} \varphi(e) = \sum_{e \in \delta^-(v)} \varphi(e) $$ at the vertex $v$, then the second sum would have to be zero as well. In your case, this is not necessarily a very limiting condition on $\varphi$; there's lots of values you could assign to those edges that would work.

(In other contexts, flows are limited to nonnegative real values, so having $\delta^+(e) = \varnothing$ would force $\varphi(e) = 0$ for all $e \in \delta^-(v)$.)