3
$\begingroup$

I have a network, with $V$ vertex, $E$ edges and $C$ cycles, which has "current" flowing in and out from the network, as shown below:

Each edge has a current value associated to it.

The equations governs the current flow in the network are the so-called "current conservation theorem", which means that all the current flowing into a node is equal to the current flowing outside from it.

For example, in the above network, such equations can be written as:

$$Q_{in}=e1+e2 \quad\quad \text{(at v1)}$$ $$e3+e13=e7+e5+e6 \quad\quad \text{(at v4)}$$ $$e8+e10=e11+Q_{out2} \quad\quad \text{(at v8)}$$

at every vertex. the node location and the value of $Q_{outi}$ are given beforehand, but only the location of $Q_{in}$ are given, the value of $Q_{in}$ is not given. $e_i$ is not known as well.

The interesting thing to note is that from the above sets of equation, one can deduce that, for any kinds of graph system, all the incoming external sources must equal to the outgoing external sources, i.e.

$$Q_{in}=Q_{out1}+Q_{out2}$$

In this way one can deduce the value of $Q_{in}$ quite easily.

Another point to note is that in a $V$ vertexes network with $E$ edges, the total number independent equations one can form from the above requirements are $V-1$. This is because if you manipulate the above equations for any kinds of graph, you will always find that there are only $V-1$ independent equations.

Thus the number of current value that one can arbitrary set is $E-(V-1)$. Recall that $C=E-V+1$, one can conclude that the number of cycles corresponds to the number of indeterminate variables.

In other words this is an indeterminate system with $E$ variables but $V-1$ independent equations.

My question is, out of all the $e1, e2, e3$ and so on, how to choose which $e_{i}$ for arbitrary value assignment ( so that the system will be reduced to a unique system, with $V-1$ variables and $V-1$ independent equations)? My hunch is that I will use all the edges that are not inside the spanning tree of the graph and set their current value arbitrarily. But I can't prove ( or disprove) this. Any ideas?

  • 0
    I think you have a minor typo in the 2nd equation: $e3+e13=e7+e5\pm e6$ (Is $e6=0$ ?).2010-11-30
  • 0
    @Americo, gotcha!! Typo fixed. Diagram updated.2010-11-30

1 Answers 1

2

Update: Upon a bit of reflection I decided that the original answer is unnecesarily long. What is really being computed is the homology of the graph. Let $C(V)$ be the vector space (over real numbers, since the flows are real) freely generated by the vertices, and $C(E)$ the vector space freely generated by the edges. We have the map $\delta: C(E) \mapsto C(v)$ which assigns to a flow (thought of as a weighted set of edges) the tuple of net flows through vertices. The question is what is it's kernel, which is of course the $H_1$ of the graph an is in fact exactly the subspace of cycles in $C(E)$.

(See the last paragraph for interpretation of what follows in this language.)

Original answer:

In fact you can certainly take any spanning tree $T$. The point is that any edge in the complement of $T$ can be completed to a cycle using edges in $T$ in a unique way, and the resulting cycles form a basis of the cycle space. This is your ambiguity.

The general statement is: Flows on the graph with prescribed sinks and sources are in bijection with the linear maps on the cycle space.

The argument is as follows:

We need two facts: Fact 1) If the flow around any cycle is zero, then the flow actually comes from a potential - that is a function $f$ on vertices, such that flow on edge e is the difference of the value of $f$ on its head and its tail. This $f$ is uniquely determined by the flow up to an overall scalar (assuming the graph is connected; start at any vertex and any value of $f$ for it and fololow edges assigning the unique possible values for $f$ as you go; the flow around cycle being zero gurantees that you never assign contradictory values). We will show that this potential is also uniquely determined, up to overall scalar, by the net flow in each vertex, and as a consequence the corresponding flow on edges is uniquely defined.

Fact 2) If the net flow at each vertex is zero (no sources or sinks) then the flow is uniquely determined by a function on the cycle space.

Proof of Fact 1. Consider the map $Fl$ sending a potential $f$ to the set of net flows at each vertex. $Fl$ is linear, and constant potentials are in the kernel. I claim that this is the whole kernel. Indeed, if there is a vertex with a maximal potential, it will have a negative net flow from it, unless all its neighbours have the same potential. As the graph is connected, the only potentials with no flow at any vertex are constant ones.

$Fl$ is a map between vector spaces of the same dimension. As the kernel of $Fl$ is one dimensional, so is the cokernel. Note that $Fl$ lands in the subset of all tuples of net flows with the zero sum (in the summ of all net flows each edge is counted twice, once with plus and once with minus). Hence $Fl$ hits any net flow tuple with total flow zero, and any such tuple of net flows comes from unique potential, up to an overall scalar, as wanted. End of proof of Fact 1.

Proof of Fact 2: Given any linear function $G$ on the cycle space, we can define the flow $E=F(G)$ on each edge $e$ to be the sum of $G(c)$ for cycles $c$ with $e$ in $c$. This of course lands in the flows with zero net flow at each vertex (this is clear by considering what happens to a dual function to any cycle $c$ and the fact that the assignment $F$ is linear). Observe that there is a basis $c_k$ of the cycle space and edges $e_k$ with $e_k$ in $c_k$ and no $c_l$ for $l \neq k$ (the edges in the complement of the spanning tree will do), so $F$ is injective. Finally, dimension count shows $F$ is an isomorphism. End of proof of Fact 2.

Now if we fix a collection of sources and sinks, this determines a unique flow $E$ which is zero on cycles by Fact 1. The difference of any flow $E'$ with these sinks and cycles and $E$ has zero net flow on each vertex, and hence corresponds to a linear function on the cycle space by Fact 2. The end.

(Of original answer.)

Comment:

What the long argument above does is as folows: One can view flows as cochains instead of chains. That is, since $C(E)$ comes with a basis, it has a prefered isomorphism $I_e$ to $\operatorname{Hom}(C(E), \mathbb{R})$. Similarly there is a prefered isomorphism $I_v$ from $C(v)$ to $\operatorname{Hom}(C(V), \mathbb{R})$. The map $\delta$ has the dual $\delta ^*:\operatorname{Hom}(C(V), \mathbb{R}) \mapsto \operatorname{Hom}(C(E), \mathbb{R})$ sending a potential (thought of as a map from vertices to $\mathbb{R}$) to its flow (there should be a (non-commutative) diagram here). Fact 1 above is that the composition $\delta \cdot I_c \cdot \delta^*$ is an isomorphism from $\operatorname{Hom}(C(V), \mathbb{R})/\operatorname{constants}$ to $\operatorname{Im} \delta$. Fact 2 is that the kernel of $\delta$ is the cycle space (or its dual). All of this presumably in some standard book.

  • 0
    @Max, *Flows on the graph with prescribed sinks and sources are in bijection with the linear maps on the cycle space*: what do you mean by **bijection** here?2010-11-30
  • 0
    Also, I realized that any spanning tree would do, not necessarily minimum spanning tree. Question updated.2010-11-30
  • 0
    What I show is that there is a special flow - the one with no net flow around any cycle, such that the difference between that flow and any other with prescribed sinks and sources is a vector space, and that vector space is isomorphic to the space of functions on the cycles. It's like having a line in the plane not through the origin. It's not a linear subspace, but if you shift it it becomes one. Same here, flows have to be shifted by $E$ and the result is linear functions on cycles.2010-11-30
  • 0
    @Max: *If the flow around any cycle is zero*-- I afraid you can't make this assumption. But you can assume that for each cycle there is a function that further constraints how the flow along each edge should behave.2010-11-30
  • 0
    @Max, I think when you add a comment that addresses me, you should put @ in front of my name, that way I won't miss your comment. Thanks.2010-11-30
  • 0
    @Max, upon a few readings I am still not too clear what you are trying to achieve. Are you trying to prove that by fixing all the flows along the edges that are *not* inside the spanning tree to a particular value ( any value) one can obtain such a set of unique equation? i.e, are you trying to prove that my hunch is correct?2010-11-30
  • 0
    @Ngu Soon Hui. What I'm proving is slightly different (although very close), and it implies your hunch. In detail: Assigning arbitrary values to edges outside a spanning tree is a way of assigning arbitrary values to cycles (each such edge is in a unigue special cycle using only it and tree edges). I like saying that flows correspond to assigning values to cycles because it does not depend on choice of a spanning tree, but it is basically equivalent.2010-11-30