Let $D = (V,A)$ connected graph, and let $M$ be the incidence matrix of $D$. I can clearly see that a circulation must be in the nullspace of $M$, because for every $v\in V$ the sum of the weights on "in" edges are equal to the sum of the weights on "out" edges. The dimension of the nullspace is $|A|-(|V|-1)$ (the rank of $M$ is $|V|-1$, because $D$ is connected). We choose a tree in $D$, there are exactly $|V|-1$ edges in there, and if we put back each edge one bye one, then every edge makes a unique cycle. I think those cycles are the basis of the nullspace, because there are exactly $|A|-(|V|-1)$ of them, but I dont know how to prove it.
Why can we choose a basis from the cycles in the nullspace of an incidence matrix
graph theorynetwork-flow
Related Question
- [Math] Properties of trees proof
- Why is there a distinct fundamental cycle for each edge not in the spanning tree
- [Math] Does removing the “heaviest” edge of all cycles in an (unweighted) graph result in a minimum spanning tree
- Prove or disprove: The edge $e$ is not included in any minimal spanning tree of G
Best Answer
Hint:
If $\ e_1,e_2,\dots, e_{|A|+1-|V|}\ $ are the edges of $\ D\ $ that are not in the tree, $\ C_i\ $ the unique cycle which edge $\ e_i\ $ forms with the edges of the tree, and $\ j\ne i\ $, then $\ e_j\ $ is not in $\ C_i\ $. Thus, if $\ K_i\ $ is the column vector corresponding to the cycle $\ C_i\ $, then $\ K_{ie_i}\ne0\ $ and $\ K_{ie_j}=0\ $ if $\ i\ne j\ $. Can you then see why $\ K_1, K_2,\dots,K_{|A|+1-|V|}\ $ must be linearly independent?