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'm reading Diestel's Graph Theory right now and came across an interesting exercise that I cannot solve. It has to do with the basis for the cut space $C^*$:

Given a graph $G$, find among all cuts of the form $E(v)$ a basis for the cut space of $G$, $C^*$.

I know that the space $C^*$ is generated by cuts of the form $E(v)$, $v ∈ V(G)$, but which cuts precisely are they?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Consider the node-arc incidence matrix $A$ for your graph $G(V, E)$, $|V|=n$, $|E|=m$. (I will now assume that your graph is directed and connected.) Initially, $A$ is an $n \times m$ matrix (a row for each node and a column for each arc), with $1$ in the position $(v,e)$ if node $v$ is the head of arc $e$, $-1$ in the position $(v,e)$ if node $v$ is the tail of arc $e$, and zero otherwise. Usually, we assume that an arbitrary row of $A$ is deleted.

The following claims hold:

  • $A$ is of full ($n-1$) row rank;
  • for any set of $(n-1)$ linearly independent columns of $A$, the arcs corresponding to these columns make up a spanning tree of $G$;
  • the null-space of the linear transformation $A$ is called the cycle space of $G$ and it is of dimension $m-n+1$ (the cyclomatic number of $G$);
  • a basis for the cycle space is obtained as follows: for any spanning tree $T$ of $G$, each out-of-tree arc $(i,j)$ creates a unique cycle if arc $(i,j)$ is concatenated to the unique in-tree $j\to i$ (undirected) path and there are exactly $m-n+1$ such cycles;
  • a simple way to obtain a cycle basis is to order the columns of $A$ so that $A=[B\quad N]$ where $B$ is an $(n-1)\times(n-1)$ submatrix of $A$ (recall, the columns correspond to a spanning tree), and then $$\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}$$ is a cycle basis where $I_{n-1}$ is the identity matrix of size $m-n+1$;
  • the orthogonal subspace of the cycle space is called the cut space and it is of dimension $m - d_{\text{null space}} = n-1$;
  • a basis for the cut-space is obtained as follows: for any spanning tree $T$ of $G$, any in-tree arc $e$ creates a unique cut of $G$ with some properly chosen set of out-of-tree arcs, and the incidence vectors of these cuts are linearly independent;
  • a simple way to obtain a cut basis is again to write $A=[B\quad N]$ where $B$ is a $(n-1)\times(n-1)$ basis and then $$\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}$$ is a cycle basis where $I_{n-1}$ is the identity matrix of size $n-1$
  • you can check that the bases are indeed orthogonal by verifying that $$\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}=0$$

The proofs of the above claims can be found in the excellent textbook: Norman Biggs: "Algebraic Graph Theory", Cambridge Mathematical Library, 1994

share|improve this answer

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.