1 files changed, 32 insertions, 0 deletions

diff --git a/answer_sheet/main.tex b/answer_sheet/main.tex
index 002a755..67e2b09 100644
--- a/answer_sheet/main.tex
+++ b/answer_sheet/main.tex
@@ -98,5 +98,37 @@ Our algorithm is then as follows;
 
 The cycle checking step, step 2 in the algorithm above uses the Union Find. Since we did not go into the detail of Union Find in the lectures we will use the naive approach which uses $\mathcal{O}(n^{2})$ operations. On top of that, we have to run Kruskal's algorithm twice for $T_{r}$ and $T_{w}$ which runs in order $\mathcal{O}(k\log(n))$ ($k$ can be substituted with the number of white edges, if higher). Overall, the runtime of the algorithm is $\mathcal{O}(n^{2} k\log(n))$.
 
+\section{Shortest-paths and min spanning trees}%
+\label{sec:shortest_paths_and_min_spanning_trees}
+
+\subsection{a}%
+\label{sub:a}
+
+We will assume the tree of shortest paths is a spanning tree (otherwise node $s$ on its own is a tree and the answer is trivial).
+
+For a graph $G = (V, E)$, we can have $T = (V, E')$ which is a tree of shortest paths and a minimum spanning tree $T' = (V, E'')$. Take any edge incident to $s$ and call it $k$. $k = (s, x)$ is the minimum weighted edge from $s$ to $x$ per definition of the tree of shortest paths. Suppose that the MST $T'$ does not include $k$. This implies that there exists a path in $T'$ $s \leadsto x$ that does not include $k$. Adding $k$ to the MST will introduce a cycle but we can break this cycle by using the Cycle property given in the Greedy Algorithms II lecture notes. Since $k = (s, x)$ is the minimum weighted edge, it will not get deleted which means MST should have included $k$ to begin with.
+
+So it is not possible for a tree of shortest paths and a MST to not share any edges.
+
+\[\begin{tikzcd}
+        {x} \\
+        {s} \\
+        & {S}
+        \arrow[from=2-1, to=3-2, dashed, no head]
+        \arrow[from=3-2, to=1-1, curve={height=24pt}, no head]
+        \arrow["{k}"', from=1-1, to=2-1, no head]
+\end{tikzcd}\]
+
+
+\subsection{b}%
+\label{sub:b}
+
+Given the acyclic digraph $G = (V, E)$ and an arborescence $A \subset E$ with the given conditions in the question text, $A$ itself is then a minimum cost arborescence in $G$. Take any $e = (v, t) \in A$. If $e$ is part of some minimum cost arborescence in $G$ then it is the cheapest incoming edge for $t$ per the lecture notes. $A$ is built up from such $e$ and the algorithm for building an arborescence in $G$ per the lecture notes is picking the cheapest incoming edge for every node and the graph $G$ is acyclic meaning that we cannot form accidental cycles by including every $e \in E$, $A$ is a minimum-cost arborescence in $G$.
+
+
+
+
+
+
 
 \end{document}