23.1-2

Consider the above example from the lecture note. If we partition the orginal graph into $\{ a, b, c, d, e, f, h, i \}, \{ g \}$, then it's clear that $(g, f)$ is a safe edge but $(g, h)$ is the only light edge.

23.2-4

1. We can apply counting sort on sorting edges by weight. Then by analysis in lecture note, total time consumption is almost linear, $O(|E| \alpha(|V|))$.
2. Similarly, $O(W + |E| \alpha(|V|))$.

23.2-5

1. We don't need heap structure anymore. Instead, we can use an adjacency list which contains |V| linked-lists for storing adjacent nodes. For instance, the $n$-th linked-list contains all nodes which are adjacent to the MST with edge weight $n$. Then, by analysis in lecutre note, total time consumption is $O(|V|) + O(|E|) = O(|E|)$.
2. Similarly, $O(W) + O(|E|) = O(W + |E|)$.

23-3

a.

Let $T$ be a minimum spanning tree of graph $G$. Assume that $T$ is not a bottleneck spanning tree. Thus, for the largest weight edge of $T$, written $(u, v)$, there exists another spanning tree $T'$ of $G$ which contains no edge with weight $\geq (u,v)$. If $(u, v)$ is removed from $T$, then it consequently cut $T$ into $2$ parts. But since $T'$ is also a spanning tree, we can find another edge $(u', v')$ from $T'$ to connect these $2$ parts and construct a new spanning tree $T''$ with $w(T) > w(T'')$. That implies $T$ is not a minimum spanning tree and leading a contradiction.

b.

It's not difficult to see the time complexity is $O(|E|)$.

CHECK-BST($G$, $b$):
  for each edge $e \in G.E$:
    if $w(e) > b$:
      discard $e$ from $G$
  if $G$ is connected (by DFS):
    return True
  else:
    return False

c.

Design:

BOTTLENECK-SPANNING-TREE($G$)
  $M :=$ largest weight in $G.E$
  $m :=$ smallest weight in $G.E$
  $b := \lfloor \frac{M + m}{2} \rfloor$
  $T := \phi$

  while $|G.V| > 1$:
    if CHECK-BST($G$, $b$):
      $M := b$
      $b := \lfloor \frac{M + m}{2} \rfloor$
    else:
      $m := b$
      $b := \lfloor \frac{M + m}{2} \rfloor$

    $G, T := $MST-REDUCE($G$,$T$)

  if CHECK-BST($G$, $b$):
    return $b$ and $T$
  else:
    return $(b+1)$ and $T$

Analysis:

1. Expect the while-loop, all operations takes $O(|E|)$ time.
2. Since at least a half nodes merges into others in each iteration of the while-loop, it makes $|E|$ shrink at least a half also (it seems true for connected graph, but I have no idea to explain). Therefore, the while-loop consumes $O(|E|) + O(|E| / 2) + O(|E| / 8) + ... \leq O(2 |E|) = O(|E|)$ time.

Hence, the time complexity is $O(|E|)$.