directed graph question

**Dinkydoe** · November 6th 2011, 08:11 AM

Let $G=(V,A)$ a directed graph with a length-function $l:A\to\mathbb{R}$ . Furthermore assume that $G$ has a vertex $v_1$ with no incoming arrows, and for all $v\in V$ there exists a path from $v_1$ to $v$

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

I've been asked to show: $G$ has a circuit with negative length $\Leftrightarrow u_j^{n}< u_j^{n-1}$ for some $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 $C= (1,\cdots r, 1)$ a circuit with negative value, and add
an arrow $(v_1, 1)$ . Then we have a graph that has exactly all desired properties.

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

Can someone make this make sense to me? :P

Thanks :/

**emakarov** · November 6th 2011, 12:10 PM

Originally Posted by Dinkydoe

I've been asked to show: $G$ has a circuit with negative length $\Leftrightarrow u_j^{n}< u_j^{n-1}$ for some $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 $u_j^{n}< u_j^{n-1}$ for some $j$ and $n$ .

Thread: directed graph question

LinkBack

Thread Tools

Display

directed graph question

Re: directed graph question

Similar Math Help Forum Discussions

Directed graph statistics

Shortest path for a directed graph including additional variable

directed acyclic graph completion time distribution

Drawing a directed graph

Algorithm to find Combinatorial Optimization of a Directed Acyclic Graph Problem

Search Tags