Expand the answer to question 1HEADmaster

1 files changed, 22 insertions, 3 deletions

diff --git a/main.tex b/main.tex
index 96c5d5b..28c54bd 100644
--- a/main.tex
+++ b/main.tex
@@ -33,10 +33,9 @@
 \section{Checking Consistency of Judgements}%
 \label{sec:checking_consistency_of_judgements}
 
-Given the collection of $n$ butterflies and a potential judgement between every pair (or not if the judgement is ambiguous), we have a graph $G = (V, E)$ with $n = |V|$ vertices and $|E| = m \le \frac{n(n-1)}{2}$ edges, with every edge $(i, j) \in E$ labelled either \enquote{same} or \enquote{different}. At the end of our algorithm, the vertices should be \emph{consistently} labelled as either \texttt{A} and \texttt{B} or our algorithm should be able to prove that $G$ cannot be labelled as so.
+Given the collection of $n$ butterflies and a potential judgement between every pair (or not if the judgement is ambiguous), we have a graph $G = (V, E)$ with $n = |V|$ vertices and $|E| = m \le \frac{n(n-1)}{2}$ edges, with every edge $(i, j) \in E$ labelled either \enquote{same} or \enquote{different}, assuming $(i,j)$ is not judged again as $(j,i)$. At the end of our algorithm, the vertices should be \emph{consistently} labelled as either \texttt{A} and \texttt{B} or our algorithm should be able to prove that $G$ cannot be labelled as so.
 
-A modified graph traversal using either BFS or DFS (since a node can be discovered multiple times in both of them) will work. Here we will modify the graph traversal given on \emph{page 42} on our \nth{3} lecture slides that uses BFS. The input of the algorithm is a node $s \in E$. If, due to ambiguous (i.e.\ missing) nodes, the graph is not connected, the algorithm should be run until every connected component is discovered.
-% TODO: run until every cc is discovered is handwavey <15-11-20, yigit> %
+A modified graph traversal using either BFS or DFS will work. Here we will modify the graph traversal given on \emph{page 42} on our \nth{3} lecture slides that uses BFS. The input of the algorithm is any node $s \in E$. If, due to ambiguous (i.e.\ missing) nodes, the graph is not connected, the algorithm should be run on a new undiscovered node until every connected component is discovered.
 
 {\centering
     \begin{minipage}{.7\linewidth}
@@ -82,6 +81,26 @@ A modified graph traversal using either BFS or DFS (since a node can be discover
 
 With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ time this algorithm has the same running time as BFS; $\mathcal{O}(m+n)$.
 
+To give a short proof, consider the scenario below;
+
+\begin{tikzpicture}[auto]
+    \node [label={[red]left:$A$}] (a) at (90:1) {$a$};
+    \node [label={[red]right:$A$}] (b) at (45:2) {$b$};
+    \node [label={[red]right:$B$}] (c) at (0:2) {$c$};
+    \node [label={[red]left:$A$}] (d) at (240:1) {$d$};
+
+    \draw (a) to node {S} (b);
+    \draw (b) to node {D} (c);
+    \draw (c) to node {?} (d);
+    \draw (a) to node [swap] {S} (d);
+\end{tikzpicture}
+
+Consider the situation where we started at node $a$ with the label \texttt{A}, labelled $b$ with \texttt{A} due to \enquote{same} $(a,b)$ edge and labelled $d$ with \texttt{A} due to \enquote{same} $(a, d)$ edge.
+Node $c$ will be labelled with \texttt{B} due to \enquote{different} $(b, c)$ edge.
+Now, depending on the judgement on (or lack thereof) $(d,c)$ edge, the graph will be either consistent (if \enquote{different})
+or inconsistent (if \enquote{same}).
+Since the modified BFS above visits every node at least once and considers every edge at least once (property of BFS), an inconsistent path will be discovered or none will occur, meaning a consistent graph.
+
 \section{Reachability}%
 \label{sec:reachability}