$\newcommand{\ddfrac}[2]{\frac{\displaystyle{#1}}{\displaystyle{#2}}}$
Exercises
Ex. 1
skipped in hope of professionally read while solving the exercises, and well-gain from lectures.
Ex. 2
To definte shortest-path weight function $\delta$, which satisfies the triangle inequality, enabling the second property of $\overline{w}$.
Ex. 3
For a cycle $c = v_0, v_1, \dots, v_k=v_0$ we are given $w(c) = 0$. It is natural to ignore the case $k = 0$.
Recall the facts
- $\overline{w}(u,v) \geq 0$
- $\overline{w}(u,v) = w(u,v) + h(u) - h(v)$
- $\overline{w}(p) = w(p) + h(v_0) - h(v_k)$ for path $p$
Lemma. $\Sigma \overline{w}(v_i, v_{i+1}) = 0$
If any $\overline{w}(v_i,v_{i+1}) > 0$ then $\overline{w}(c) > 0$, contradicting the proved above lemma.
Ex. 4
skipped in hope of professionally read while solving the exercises, and well-gain from lectures.
Ex. 5
In page 636 there is a hint of using fibonacci-heabs. I am not sure whether it is the key of solving the problem. Anyway, The exercise is postponed untill we gain a guidance from others. Skimming the chapter did not yield any promising clue to pursue.
Ex. 6
Same as Ex. 5
Problems
Prob. 1
a
Case $r = w_{i,j}$. Nothing to be done.
Case $r < w_{i,j}$. Check to see if new paths including edge $(i,j)$ offer less-weight.
(For LaTeX issue we denote matrix $\Pi$ by $P$)
for x = 0 to n
for y = 0 to n
if d_x,i + r + d_j,y < d_x,y
d_x,y = d_x,i + r + d_j,y
P(x,j) = i
P(x,y) = P(j,y)
Observe $\Pi(x,i)$ is the same, and same for its recursive vertices. Similarly to $\Pi(j,y)$.
Complexity. $\mathcal{O}(V^2)$
Case $r > w_{i,j}$. For paths which do not depend on $w_{i,j}$, Nothing needs to be updated about them. If their paths are less or equal than any path which includes $w_{i,j}$ then obviously these paths are still optimal when the weight of $w_{i,j}$ increases. If for vertex $x$, $P(x,j) != i$ then $x$ shall never visit edge $\set{i,j\}$.
Our focus starts on vertices $x$ whose $\Pi(x,j)$ equals $i$. For each such $x$ and each arbitrary vertex $y$, We compute minimum paths from $x$ to $y$ and update if needed. Let $D'$ and $\Pi'$ denote minimum distance and predecessor matrices after updating the weight of edge $\set{i,j\}$ to $r$, respectively. Any path $x \rightarrow y$ either consists of a single edge $\set{x,y\}$ or contains an intermediate vertex between $x$ and $y$. We loop on all vertices $z$ to compute $D(x,z) + D(z,y)$ and then set $D'(x,y)$. However, we must check whether edge $\set{i,j\}$ falls into the path $x \rightarrow z$ or $z \rightarrow y$. if NO, then we know $D'(x,z) = D(x,z)$ and $D'(z,y) = D(z,y)$. If YES, then the new weight of path $x \rightarrow y$ which equals $D(x,y) + (r-w_{i,j})$, is equal or less than the new weight $D(x,z) + D(z,y) + (r - w_{i,j})$. That follows by $D(x,y) \leq D(x,z) + D(z,y)$ as the additional weight $r - w_{i,j}$ is added on both sides of the inequality. In this case we know $z$ won’t offer a less-weight path. So we can restrict our focus on vertices $z$ whose corresponding paths do not include edge $\set{i,j\}$.
(For LaTeX issues we denote matrix $\Pi$ by $P$)
isEdgeInPath(edge {i,j}, path x -> y, predecessor P)
if P(x,j) != i
return False
s = y
while P(x,s) != x
if P(x,s) == j
return False
return True
Main()
for x = 0 to n
if P(x,j) = i
for y = 0 to n
minDistance = min{ edge (x,y) if exists, D(x,y) + (r - w_i,j) }
minVertex = NULL
isDistanceUpdated = False
for z = 0 to n
if isEdgeInPath( {i,j}, x -> y, P) OR z = x OR z = y
continue to next iteration of z
zDistance = D(x,z) + D(z,y)
if (distance < minDistance)
minDistance = zDistance
minVertex = z
isDistanceUpdated = True
if isDistanceUpdated
P'(x,y) = P(z,y)
P'(x,z) = P(x,z)
Complexity. $\mathcal{O}(V^3)$
b
c
In the same mannger matrices $M$ and $\Pi$ are maintainces distances and predecessors, We maintain also matrix $W$ for the number of edges corresponding to $d_{i,j}$ in $M$. The algorithm then checks $W$ before updating a new solution whether its number of edges is at most $h$.
Complexity. The overhead is constant over the original algorithm. In terms of parameters and $h$ is postponed.
d
The algorithm constructs a series of matrices $L^1, L^2, .., L^{n-1}$ where $L^m = \left ( l_{ij}^m \right )$, indicating shortest-paths of edges length at most $m$. The adapted algorithm terminates on $L^{h}$ and outputs it.
Complexity. At most the complexity of the original algorithm.
e
Prob. 2
a
We prove if there are two different minimum spanning trees, $T_a$ and $T_b$, Then we can construct a minimum spanning tree $T_c$ whose weight is less than either of them.
We define:
- $E_a = T_a(E)$
- $E_b = T_b(E)$
- $E_c = E_a \cap E_b$
- $E_{a-b} = E_a - E_b$
- $E_{b-a} = E_b - E_a$
- $E_{-c} = E_{a-b} \cup E_{b-a}$
- $e_{a}$, An edge in $E_a$
- $e_{a0}$, An edge in $E_{a-b}$
Lemma. For an edge $e_{a0} = \{x,y\}$, $x$ and $y$ are connected by a path in $T_b$ which does not include edge $e_{a0}$. Similarly for $e_{b0}$.
Follows immediately as by definition $e_{a0} \not\in E_b$.
Lemma. For an edge $e_{a0} = \{x,y\}$, There exists distinct edges $e_{b}^1$ and $e_{b}^2$ such that $e_b^1$ joins $x$ and $e_b^2$ joins $y$ in $E_b$. Similarly for $e_{b0}$.
Follows immediately by Lemma 1. Note the two edges $e_{b}^1$ and $e_{b}^2$ can share at most one vertix.
Lemma. If there is a cycle where all edges are in $E_a$ except exactly one edge $e_b$ in $E_b$, and $w(e_b) < w(e_a^i)$ for some $e_a^i$ in the cycle, then we can construct a MST $T_a' = T_a - e_a^i + e_b$ of weight less than $T_a$
Consider two vertices, $v_1$ and $v_2$, whose connectivity relies on edge $e_a^i = \{x,y\}$. The path is $p(v_1,x), (x,y), p(y,v_2)$. By adding $e_b$ we know there is path $p_0(x,y) \neq (x,y)$, i.e $x$ can reach $y$ without edge $(x,y)$. Therefore we can form an alternative path for $v_1$ and $v_2$ without relying on $(x,y)$ by $p(v_1,x), p_0(x,y), p(y,v_2)$. Thus, Removing $e_a^i$ is safe. Note It is clear neither $p(v_1,x)$ nor $p(v_2,x)$ contains edge $(x,y)$ as that means there is an unnecessary cycle in the path.
Clearly $E_{-c}$ is non-empty, Otherwise $T_a = T_b$. Without the loss of generality, Assume the selected element of $E_{-c}$ is $\{x,z\} = e_{a0} \in E_{a-b}$. There are only two cases regarding the weight of $e_{a0}$.
Case 1: $w(e_{a0}) = 0$. By Lemma 1 we know there is a path $p(x,y)$ which does not include $e_{a0}$. Clearly have a circle of, edges in $E_b$ and exactly one edge in $E_a$. Since all weights of the graph are distinct and non-negative, $w(e_{a0})$ is strictly less than all edges in the circle. By Lemma 3, We can form a lower-weight MST. Contradiction.
Case 2: $w(e_{a0}) > 0$. By Lemma 2 we get edges $e_{b}^1$ and $e_{b}^2$ in $E_b$ where they contain vertices $x$ and $y$. Clearly it is not possible for both $e_b^1$ and $e_b^2$ to be in $E_a$. Otherwise we would have a cycle in $T_a$ contradicting the fact a tree has no cycles. It is easy to justify it by considering $T_a' = T_a - e_{a0}$. Without the loss of generality assume $e_b^1 \not\in E_a$, i.e $e_b^1 = e_{b0}^1$. Denote $e_{b0}^1$ by $\{y,z\}$.
We claim there is a cycle of edges including $e_{b0}$ and $e_{a0}$, Where all remaining edges are in $E_a$. By connectivity of $T_a$ we know there is a path in $T_a$ between $x$ and $z$. Note the cycle is totally legit if it contained $y$. Similarly, There is a cycle of edges including $e_{a0}$ and $e_{b0}$, Where all remainig edges are in $E_b$.
We know $e_{a0} \neq e_{b0}$. In either cases some edge is greater than the other. By Lemma 3, We get a lower-weight spanning tree. Contradiction.
b
Correctness. For any graph $G$, There is a unique sub-graph $G_c$, Such that for any cycle $c$ in $G$ whose all edges are in $G_c$ except for exactly one edge $e_x$, The weight of $e_x$ is the maximum along the whole cycle of $c$. The proof is nearly identical to a.
Clearly the MST exerts this property lest we construct another spanning-tree of less weight. Since the algorithm claimed here always prefers less-weight edges, It shall never contradict that property also. By uniqueness the claimed algorithm yields the MST.
Algorithm Description.
Complexity Analysis.
c
Counter-example:
d
Correctness. Yes. The proof is nearly identical to a.
Algorithm Description.