A&D assignment 12

exercise

12.1 MST practice

a)

After the first step: $(A,B)$ $(C,H),(D,H),(E,H),(F,I),(G,H),(H,I)$ After the second step: $(A,B),(C,H),(D,H),(E,H),(F,I),(G,H),(H,I),(B,C)$

b)

$(A,B),(D,H),(C,H),(B,C),(H,I),(F,I),(G,H),(E,H)$

c)

$(G,H),(D,H),(C,H),(B,C),(A,B),(H,I),(F,I),(E,H)$

12.3 Uniqueness of MSTs

a)

not unique MST.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

A

B

C

1

1

1

Link to original

We can get MST $(A,B),(B,C)$ from Kruskal’s algorithm, and $(A,C),(B,C)$ from Prim’s algorithm

b)

Since $T_2$ is a spanning tree, adding an extra edge $e\notin T_2$ creates exactly one cycle: Assume $e$ connects $u$ and $v$. There exists a path from $u$ to $v$ through the spanning tree (without using $e$). If we add $e$ to this path, we get a cycle.

We claim this cycle to be $C$. There must be an edge $f\in T_2\setminus T_1$ on $C$, because otherwise $C$ would be fully contained in $T_1$, which contradicts the fact that $T_1$ is a spanning tree. Moreover, $f$ could not be $e$, because $e\in T_1\setminus T_2$. So $f$ and $e$ are distinct. Since all weights are distinct and $e$ is the minimum weight, we have $w(f)>w(e)$

c)

We replace $f$ with $e$ on $T_2$. We first add $e$ to $T_2$ and get a cycle $C$, then we remove another edge $f$ on this cycle, such that the remaining structure is still a spanning tree (every vertices are still connected and no more cycles). Now we’ve reduced the total weight of $T_2$ by $w(f)-w(e)$ (not $0$). This leads to a contradiction to our assumption that $T_2$ is a minimum spanning tree. Therefore, the minimum spanning tree of $G$ with weight function $w$ is unique.

d)

Not unique weight of MST.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

A

B

C

1

1

Link to original

There is one unique minimum spanning tree $(A,B),(B,C)$, however, the weights are not distinct.

12.4 Counting Minimum Spanning Trees With Identical Edge Weights

a)

Contracting an edge $e\in T$ just “glues together” its two endpoints. Since $T$ is a tree, this operation does not create cycles or disconnect the graph. So the contracted tree $T_e$​ is still a spanning tree of the contracted graph $G_e$​ . Now we show that $T_e$ is minimal. Suppose we uncontract $e$ (separate $vw$, and add back the original edges). The total weight increases by exactly $c(e)$ .If there were a spanning tree of $G_e$ cheaper than $T_e$, then uncontracting it would give a spanning tree $G$ cheaper than $T$, which contradicts the fact that $T$ is minimal.

b)

We partition $E$ into weight classes. we define $E_{\alpha }=\{e\in E|w(e)=\alpha \}$ An edge $f$ is redundant if it lies in a class of size at least $2$. ($e\ne e^{\prime }\in E$ with $w(e)=w(e^{\prime })$) Let $\alpha =w(e)$. In $G_e$, the only weight class whose size changes is $E_{\alpha }$, which becomes size $|E_{\alpha }|-1$. Case 1: $|E_{\alpha }|=2$, then the redundancy drops by 2. $k^{\prime }=k-2$ because $E_{\alpha }$ now has size of 1 and does not contribute to the overall redundancy. Case 2: $|E_{\alpha }|\ge 3$, then the redundancy drops by 1. $k^{\prime }=k-1$ Therefore, the number of redundant edges in $G_e$ is at most $k-1$ Hence, $G_e$ is $k^{\prime }$-redundant for some $k^{\prime }\le k-1$

c)

We prove by induction Claim: If $G$ is connected and k-redundant, it has at most $2^k$ distinct MSTs. Base: $k=0$: If $k=0$, then all edges are pairwise distinct, so MST is distinct (result from 12.3). The number of distinct MST is $1\le 2^0=1$

Step: $k\to k+1$ we assume if $G$ is connected and k-redundant, it has at most $2^k$ distinct MSTs Consider a (k+1)-redundant $G$: we pick a redundant edge $e$ We denote the number of distinct MSTs that contains $e$ with $\#T^{\prime }$ We denote the number of distinct MSTs that does not contains $e$ with $\#T^{\prime \prime }$

case 1 $e\in T$ by (a) the contracted tree $T_e$ is an MST of $G_e$, so $\#T^{\prime }\le |MST(G_e)|$ by (b), $G_e$ is at most ((k+1)-1)-redundant. So we have $\#T^{\prime }\le |MST(G_e)|\le 2^{(k+1)-1}=2^k$ case 2 $e\notin T$ Consider $G\setminus e$. Any MST $T$ with $e\notin T$ is still a spanning tree of $G\setminus e$. Hence we have: $\#T^{\prime \prime }\le |MST(G\setminus e)|$ we know deleting a redundant edge decreases the number of redundant edges by at least 1 so $\#T^{\prime \prime }\le |MST(G\setminus e)|\le 2^k$ Conclusion the number of distinct MSTs $=\#T^{\prime }+\#T^{\prime \prime }\le 2^k+2^k=2^{k+1}$ We’ve now shown that there are at most $2^{k+1}$ distinct MSTs.

The claim is proved through induction.