Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I think you have a minor typo in the 2nd equation: $e3+e13=e7+e5\pm e6$ (Is $e6=0$ ?). –  Américo Tavares Nov 30 '10 at 15:11
    
@Americo, gotcha!! Typo fixed. Diagram updated. –  Graviton Nov 30 '10 at 15:14

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
@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? –  Graviton Nov 30 '10 at 15:02
    
Also, I realized that any spanning tree would do, not necessarily minimum spanning tree. Question updated. –  Graviton Nov 30 '10 at 15:03
    
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. –  Max Nov 30 '10 at 15:13
    
@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. –  Graviton Nov 30 '10 at 15:22
    
@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. –  Graviton Nov 30 '10 at 15:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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