Chapter 24, Problem 5P

(a)

Program Plan Intro

To show that if μ *=0 then the graph should not contains any negative weight cycle and ξ_k(s, v), v ∈ V .

(b)

Program Plan Intro

To show that if $\mu *=0$ then $\frac{\delta n\left(s,v\right)-\delta k\left(s,v\right)}{n-k}\ge 0$ , k ∈ (0,…., n -1), for all v ∈ V .

(c)

Program Plan Intro

To prove that $\delta \left(s,v\right)=\delta \left(s,u\right)+x$ , if x is the weight of path from vertex u to vertex v on 0-weight cycle.

(d)

Program Plan Intro

To show that μ *=0 then $\frac{\delta n\left(s,v\right)-\delta k\left(s,v\right)}{n-k}\ge 0$ , k ∈ (0,...., n -1), for all v∈ Von every minimum mean weight cycle.

(e)

Program Plan Intro

To show that if μ *=0, $\underset{v\in V}{\min }\underset{0\le k\le n-1}{\max }\frac{{\delta }_n\left(s,v\right)-{\delta }_k\left(s,v\right)}{n-k}=0$ .

(f)

Program Plan Intro

To show if a constant t is added to weight of each edge of G , then μ *increases by t . Also show $\mu *=\underset{v\in V}{\min }\underset{0\le k\le n-1}{\max }\frac{{\delta }_n\left(s,v\right)-{\delta }_k\left(s,v\right)}{n-k}$

(g)

Program Plan Intro

To provide an algorithm that takes O (VE) time to evaluate μ *.