Introduction

Welcome to this sample article. Here, we’ll explore various Markdown elements rendered in an Apple News-inspired design.

Chapter 4

Exercise 2

(a) This statement is true. If we treat the edges with Kruskal algorithm, the edges with costs of $c_e^2$ shares the same order with $c_e$. And hence the subset of edges in the MST is the same.

(b) This statement is false. Suppose we have $3$ edges $(u,v,3),(v,w,3),(u,w,5)$, then the shortest path length of $(u,w)$ is $e_{(u,w)} = 5$. But after the edge costs become their squares, $(u,v,9),(v,w,9),(u,w,25)$, the shortest path of $(u,w)$ becomes $e_{(u,v)}+e_{(v,w)} = 18$.

Exercise 8

We will prove the statement using contradiction.

Suppose we have two different MST $T, T’$. Then there is some edge $e’$ in $T’$ but not in $T$. Let’s add $e’$ into $T$, then there must appear a cycle. The largest edge on this cycle should not be in any MST of $G$, neither $T$ or $T’$. So there is a contradiction. So the MST of $G$ is unique.

Exercise 22

Consider a graph below:

All $5$ edges belong to an MST, but any subset of ${(u,v),(v,w),(w,x),(x,v)}$ could not form an MST.

So the statement is false.