From 18539f03d200fb94d59f102207213c3c80cdc5d7 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Wed, 2 Dec 2020 00:29:04 +0300
Subject: Include the answer to third question

both a and b
---
 answer_sheet/main.pdf      | Bin 169720 -> 194172 bytes
 answer_sheet/main.tex      |  32 ++++++++++++++++++++++++++++++++
 answer_sheet/quiver.sty    |  36 ++++++++++++++++++++++++++++++++++++
 answer_sheet/structure.tex |   1 +
 4 files changed, 69 insertions(+)
 create mode 100644 answer_sheet/quiver.sty

(limited to 'answer_sheet')

diff --git a/answer_sheet/main.pdf b/answer_sheet/main.pdf
index 7e9b4c4..5d1a4d4 100644
Binary files a/answer_sheet/main.pdf and b/answer_sheet/main.pdf differ
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}
diff --git a/answer_sheet/quiver.sty b/answer_sheet/quiver.sty
new file mode 100644
index 0000000..57d154b
--- /dev/null
+++ b/answer_sheet/quiver.sty
@@ -0,0 +1,36 @@
+% *** quiver ***
+% A package for drawing commutative diagrams exported from https://q.uiver.app.
+%
+% This package is currently a wrapper around the `tikz-cd` package, importing necessary TikZ
+% libraries, and defining a new TikZ style for curves of a fixed height.
+%
+% Version: 1.0.1
+% Authors:
+% - varkor (https://github.com/varkor)
+% - AndréC (https://tex.stackexchange.com/users/138900/andr%C3%A9c)
+
+\NeedsTeXFormat{LaTeX2e}
+\ProvidesPackage{quiver}[2020/11/27 quiver]
+
+% `tikz-cd` is necessary to draw commutative diagrams.
+\RequirePackage{tikz-cd}
+% `calc` is necessary to draw curved arrows.
+\usetikzlibrary{calc}
+% `pathmorphing` is necessary to draw squiggly arrows.
+\usetikzlibrary{decorations.pathmorphing}
+
+% A TikZ style for curved arrows of a fixed height, due to AndréC.
+\tikzset{curve/.style={settings={#1},to path={(\tikztostart)
+    .. controls ($(\tikztostart)!\pv{pos}!(\tikztotarget)!\pv{height}!270:(\tikztotarget)$)
+    and ($(\tikztostart)!1-\pv{pos}!(\tikztotarget)!\pv{height}!270:(\tikztotarget)$)
+    .. (\tikztotarget)\tikztonodes}},
+    settings/.code={\tikzset{quiver/.cd,#1}
+        \def\pv##1{\pgfkeysvalueof{/tikz/quiver/##1}}},
+    quiver/.cd,pos/.initial=0.35,height/.initial=0}
+
+% TikZ arrowhead/tail styles.
+\tikzset{tail reversed/.code={\pgfsetarrowsstart{tikzcd to}}}
+\tikzset{2tail/.code={\pgfsetarrowsstart{Implies[reversed]}}}
+\tikzset{2tail reversed/.code={\pgfsetarrowsstart{Implies}}}
+
+\endinput
diff --git a/answer_sheet/structure.tex b/answer_sheet/structure.tex
index 77d3e4c..5a9fcbe 100644
--- a/answer_sheet/structure.tex
+++ b/answer_sheet/structure.tex
@@ -34,6 +34,7 @@
 \usepackage{caption}
 \usepackage{tikz}
 \usepackage{subcaption}
+\usepackage{quiver}
 \usetikzlibrary{arrows,fit,positioning}
 \usepackage[style=authoryear]{biblatex}
 
-- 
cgit v1.2.3-70-g09d2