directed graph question

• Nov 6th 2011, 08:11 AM
Dinkydoe
directed graph question
Let $\displaystyle G=(V,A)$ a directed graph with a length-function $\displaystyle l:A\to\mathbb{R}$. Furthermore assume that $\displaystyle G$ has a vertex $\displaystyle v_1$ with no incoming arrows, and for all $\displaystyle v\in V$ there exists a path from $\displaystyle v_1$ to $\displaystyle v$

Let $\displaystyle u_j^k$ be the length of the shortest path from $\displaystyle v_1$to $\displaystyle v_j$ with at most $\displaystyle k$ arrows.

I've been asked to show: $\displaystyle G$ has a circuit with negative length $\displaystyle \Leftrightarrow u_j^{n}< u_j^{n-1}$ for some $\displaystyle j$

(the question doesn't say if it's for all n or not, but I assume that's what they mean).

I think that it's nonsense, since I think the following is a counterexample:
Let $\displaystyle C= (1,\cdots r, 1)$ a circuit with negative value, and add
an arrow $\displaystyle (v_1, 1)$. Then we have a graph that has exactly all desired properties.

But now we have $\displaystyle u_j^{j+nr}< u_j^{j+nr-1}$ for all $\displaystyle n$ for all $\displaystyle j\in C$. But it's not true that $\displaystyle u_j^n<u_j^{n-1}$ for all $\displaystyle n$ ( for most $\displaystyle n$ we have $\displaystyle u_j^{n-1}= u_j^{n}$).

Can someone make this make sense to me? :P

Thanks :/
• Nov 6th 2011, 12:10 PM
emakarov
Re: directed graph question
Quote:

Originally Posted by Dinkydoe
I've been asked to show: $\displaystyle G$ has a circuit with negative length $\displaystyle \Leftrightarrow u_j^{n}< u_j^{n-1}$ for some $\displaystyle j$

(the question doesn't say if it's for all n or not, but I assume that's what they mean).

I think the claim is that G has a circuit with negative length iff $\displaystyle u_j^{n}< u_j^{n-1}$ for some $\displaystyle j$ and $\displaystyle n$.