How to prove this equation?

  • #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.
 

Answers and Replies

  • #2

Homework Statement


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)##

Homework Equations


This is the part I can't figure out

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:

Related Threads on How to prove this equation?

  • Last Post
Replies
3
Views
2K
Replies
8
Views
1K
Replies
4
Views
6K
Top