Results 1 to 2 of 2

Math Help - directed graph question

  1. #1
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411

    directed graph question

    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 :/
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: directed graph question

    Quote Originally Posted by Dinkydoe View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Directed graph statistics
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 10th 2011, 12:19 PM
  2. Replies: 0
    Last Post: April 28th 2010, 10:26 PM
  3. directed acyclic graph completion time distribution
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: August 14th 2009, 11:28 PM
  4. Drawing a directed graph
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2008, 08:38 AM
  5. Replies: 0
    Last Post: November 6th 2007, 02:05 PM

Search Tags


/mathhelpforum @mathhelpforum