1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove this equation?

  1. Dec 12, 2014 #1
    • Member warned about not using the homework template
    Prove ##\displaystyle \lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)##
    Prove the minimum directed cycle mean cost satisfies: ##\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)## using the Bellman-Ford algorithm.


    Let ##\mathcal G = (\mathcal V, \mathcal A)## be directed graph with associated edge costs ##c_{i,j}## that has at least one directed cycle (##c_{i,j} = \infty## for all ##(i,j) \notin \mathcal A##).


    Define the directed cycle mean cost to be ##\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}##.


    Set ##p_i(0) = 0## and ##p_i(t+1) = \min_{j \in O(i)} \{ c_{i,j} + p_j(t) \}## for all ##i\in \mathcal V##.


    I've proven by induction that ##p_i(t)## denotes the length of the shortest walk start starts at ##i## and traverses ##t## arcs.


    Now, I want to prove that the minimum directed cycle mean cost ##\lambda## satisfies:


    ##\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)##, where ##n## is the number of vertices in the graph ##\mathcal G##.


    I see that traversing ##n## arcs will always create a directed cycle. However, I don't know how to continue from here.
     
  2. jcsd
  3. Dec 13, 2014 #2
    1. The problem statement, all variables and given/known data
    Prove ##\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)##

    2. Relevant equations
    This is the part I can't figure out

    3. The attempt at a solution
    Prove the minimum directed cycle mean cost satisfies:
    ##\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)##using the Bellman-Ford algorithm.

    Let ##\mathcal G = (\mathcal V, \mathcal A)## be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle (##c_{i,j} = \infty## for all ##(i,j) \notin \mathcal A##).

    Define the directed cycle mean cost to be ##\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}##.

    Set ##p_i(0) = 0## and ##p_i(t+1) = \min_{j \in O(i)} \{ c_{i,j} + p_j(t) \}## for all ##i\in \mathcal V##.

    I've proven by induction that ##p_i(t)## denotes the length of the shortest walk start starts at ##i## and traverses ##t## arcs.

    Now, I want to prove that the minimum directed cycle mean cost ##\lambda## satisfies:

    ##\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)##, where ##n## is the number of vertices in the graph ##\mathcal G##.

    I see that traversing ##n## arcs will always create a directed cycle. However, I don't know how to continue from here.
     
    Last edited: Dec 13, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to prove this equation?
  1. Prove the equation (Replies: 1)

  2. How to prove? (Replies: 3)

  3. Proving a equation (Replies: 13)

Loading...