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 am trying to prove that an algorithm can be devised to guarantee that absolute value of the difference between the sum of incoming edges and outgoing edges for each vertex is less than or equal to 1. The in and out edges for each vertex have to be played with.

Note: We cannot delete an edge and can only play with the direction, incoming can be converted to outgoing and vice-versa.

Thanks, Mayank

share|improve this question
    
You'll need to specify what sorts of operations you want to allow. If anything goes, then a trivial solution is to remove all the edges. –  joriki Sep 20 '12 at 11:19

2 Answers 2

Warning: long reasoning ahead. Short version in a commentary below.

Call the number (out degree - in degree) the index of a vertex. I'm assuming that the graph is finite and connected.

You can assign directions to an undirected graph inductively like this: For two vertices it's easy, just let half of the edges go one way and the other half the other. If there's an odd number of edges between them, one of them will now have index 1, the other -1.

Assume you have directions for all edges within a connected subgraph $S$ and want to find directions for all edges between a vertex $v$ and $S$. Firstfor each vertex of $S$ with more than one edge connected to $v$, label an even number of them in alternating directions. This changes no indexes, and $v$ now only has at most one unassigned edge to any vertex of $S$.

Let $S_-$ be the set of vertices of $S$ connected to $v$ with index $-1$, and define $S_0$ and $S_+$ similarly. For us to be able to assign directions to the edges between $v$ and $S$ we need $\Big||S_+| - |S_-|\Big| \leq |S_0| + 1$. For if this is fulfilled, we assign an edge to go from $v$ to all vertices in $S_+$, to $v$ from all vertices of $S_-$, and use the vertices of $S_0$ to soak up the difference.

Assuming that is is not fulfilled, and further assume wlg that $|S_+| - |S_-| > |S_0| + 1$ (wlg in this case means that were it the other way around, change directions of all edges in $S$) we need a way to alter the directions of edges in $S$ so that it is fulfilled. Now for each vertex of $S_-$, choose a vertex of $S_+$, and connect each of them to $v$ the obvious way. We're now left with only edges to vertices of $S_+$ and $S_0$ left to assign, and $v$ has a temporary index of $0$. So ignoring the unassigned edges, $S\cup {v}$ is a directed graph satisfying your criterion.

Note that the sum of indexes of the vertices of $S$ is $0$, so the number of vertices with index $1$ and the number of vertices with index $-1$ is the same. I would like to find (and will find in the next paragraph) that for any vertex of $S_+$, you can find a path to a vertex with degree $-1$ (which is not in $S_-$, since that set is now empty). If you can, then swap the direction of all arrows along that path, and you have swapped the index of the two vertices without touching the index of any other vertex. If you now assign directions to the former-$1$-but-now-$(-1)$-index vertex, as well as another vertex of $S_+$ the obvious way, this operation will reduce the number of unassigned edges of $S_+$ by two. Applying the process enough times will make it so that $|S_+| = |S_0|+ 1$ or $|S_+| = |S_0|$, and you can easily assign the rest of the arrows.

Now, assume we're sitting at a vertex $w$ with index $1$. That means we have one more out-going than in-going edges. Let $A_0 = {w}$, and define recursively $A_{n+1}$ to be the union of $A_n$ and the set of vertices pointed to by an edge from $A_n$. That means that $A_n$ is the set of vertices reachable from $w$ by traversing at most $n$ edges along their direction. I want to show that there is a $k$ such that $A_k$ contains a vertex of index $-1$. Let the total index of $A_n$ be the sum of indexes of vertices of $A_n$. As long as $A_n$ does not contain any vertices of index $-1$, it will have at least one edge pointing out of the set. Therefore, $A_{n+1}$ contains a strictly larger set of vertices. If the $A_n$ stops growing, then the total index cannot be positive, so it must contain at least one vertex of index $-1$. But since the graph is finite, the $A_n$'s has to stop growing at some point.

So we've found that there is a path from any vertex of index $1$ to a vertex of index $-1$, we can now swap the direction of any edge along that path, and this will result in the index of those two vertices swapping.

share|improve this answer
    
Short version: Start with an undirected graph, assign directions to each line by induction, starting step has 2 vertices. Here it's easy to see a direction assignment is possible. Induction step: Say you have assigned directions to all lines of a subgraph $S$, and you want to assign directions to all lines of $S\cup \{v\}$ for a vertex $v$. Separate the lines connecting $v$ to $S$ in three groups, depending on the index of the vertex in the other end. Hope that these aren't too different in size. If it turns out they are, change direction of some lines in $S$ so they aren't any more. Rejoice. –  Arthur Sep 20 '12 at 14:15

Hint: First do it in a graph with two vertices

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.