Problem2C

Problem2C: Let {G} be a directed simple graph with vertices {x_{1},\ldots ,x_{n}} for which a (directed) Eulerian circuit exists. A spanning arborescence with root {x_{i}} is a spanning tree {T} of {G}, with root {x_{i}}, such that for all {j\neq i} there is a directed path from {x_{j}} to {x_{i}} in {T}. Show that the number of spanning arborescences of {G} with root {x_{i}} does not depend on {i}.

Solution: A directed Eulerian graph {G} is a graph with a directed Eulerian circuit. Denote by {r_{i}} the number of edges going out of a vertex {x_{i}}, and {s_{i}} the number of edges going to {x_{i}}. Then a graph {G} is a directed Eulerian graph iff {r_{i}=s_{i}} for every {i}. Denote by {A_{i}} the number of spanning arborescences with root {x_{i}}. We will show that the number of Eulerian circuits of {G} is

\displaystyle  A_{i}\prod_{j=1}^{n}\left( r_{j}-1\right) !.

Hence the value of {A_{i}} does not depend on {i}.

There are three steps to show it. First, we implement an algorithm to produce different Eulerian circuits from a spanning arborescence rooted as { x_{1}}. For {i\neq 1}, the process is the same. Second, we show the reason why distinct spanning arborescences with the same root cannot produce the same Eulerian circuit. Last, the algorithm is reversible in the sense that given an Euerian circuit, we can find the spanning arborescence producing it. Hence all the Eulerian circuits are found. Now we explain in detail.

First, denote an Eulerian circuit by a sequence of edges. Note that cyclic shift of the edge sequence of an Eulerian circuit produce the same circuit. To avoid repetition of counting the Eulerian circuits, we can fix an edge going out of {x_{1}} as the first edge in the edge sequence. (why? 1. Every Eulerian circuit passes that edge; 2. Any distinct sequence then is a distinct Eulerian circuit since the first edge is fixed.) Given a spanning arborescence with root {x_{1}}, we label by {r_{j}} the edge going out of { x_{j}} ({j\neq 1}) and which is also an edge of the spanning arborescence. Then we label arbitrarily by {\left\{ 1,2,\ldots ,r_{j}-1\right\} } on the remaining {r_{j}-1} edges going out of {x_{j}} for every {j} (We do not label the edge going out of {x_{1}} as the first edge of the Eulerian circuit). So there are {\prod_{j=1}^{n}\left( r_{j}-1\right) !} difference ways of labelling. The algorithm is as follows. We start from the first edge, and always choose the unused edge with smallest label as the the next edge in the edge sequence to produce the Eulerian circuit. The process can only terminate at {x_{1}}, since the number of edges going into a vertex equals the the number of edges going out. If the algorithm terminates at { x_{1}}, all the edges going into {x_{1}} are used. So all the edges from the neighbor vertex to {x_{1}} and which is from the spanning arborescence are used. According to the algorithm, all edges going out of the vertices with distance {1} to {x_{1}} in the spanning arborescence are used, so do all the edges going into these vertices. Then by induction, all the edges going out and in to the vertices of the spanning arborescence are used, hence all edges are used. So the edge sequence is an Eulerian circuit. Note that distinct labelling will result in distinct Eulerian circuit.

Second, we show the distinction of Eulerian circuits from different spanning arborescences with the same root. We can assume that the two Eulerian circuits start from the same edge. Given two distinct spanning arborescences {T_{1}} and {T_{2}}, there always exists a vertex {x_{k}}, such that there are two distinct edges {e_{1}}, {e_{2}} going out of {x_{k}}, and {e_{1}\in T_{1}}, {e_{2}\in T_{2}}. Hence by the algorithm, we label {e_{1}} by {r_{k}} for Eulerian circuits from {T_{1}}, and label {e_{2}} by {r_{k}} for Eulerian circuits from {T_{2}}. It is easy to see that different labelling result in different Eulerian circuits if the starting edge is fixed.

Last, given an Eulerian circuit, pick a vertex and an edge going out of the vertex as the first edge in the edge sequence of the Eulerian circuit. We label the edge going out of {x_{k}} by {h} if it is the {h} edge the circuit passes. We include the edge with labelling {r_{k}} going out of {x_{k}}, for any {k\neq 1}, to form a subgraph of {G}. We claim that this subgraph is a spanning arborescence. The reasons are as follows. No cycle which does not contain {x_{1}} can be contained in the subgraph, since that all the edges of the cycle are the last one the Eulerian circuit passes can not happen, otherwise the Eulerian circuit cannot go back to {x_{1}}. Furthermore, no edge going out of {x_{1}} is involved in the subgraph, so there is no cycle containing {x_{1}} too. Since there is exactly an edge going out of every vertex, and no cycle contained, we can start a path from any vertex, then the path can keep going until reaches {x_{1}}. So there is a path from each vertex of the subgraph to {x_{1}}. Regardless of the direction of edges, we know that the spanning arborescence is a spanning tree. The path is unique otherwise regardless of the direction of edges, a cycle will be formed, which contradicts to the definition of tree. Thus it is a spanning arborescence with root {x_{1}} of {G}. Easy to see from this spanning arborescence of {G} and the labelling, we can obtain the original Eulerian circuit.

Note: Many thanks to Xinmei and ming ming for fruitful discussion of this difficult problem.

Advertisements

2 Comments (+add yours?)

  1. Tan Ming Ming
    Jul 22, 2011 @ 09:48:08

    Didn’t help at all haha…
    Nice solution!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: