Finish assignment 4

1 files changed, 31 insertions, 3 deletions

diff --git a/assignment4.tex b/assignment4.tex
index d478b7d..61aba7b 100644
--- a/assignment4.tex
+++ b/assignment4.tex
@@ -326,17 +326,45 @@
 
         We only visit every edge once, so this is done in linear time. 
 
-    \item %todo
+    \item Place a pointer at the top left of the adjacency matrix, at the edge $(0,0)$. Then, walk towards the bottom right using the following rules:
+
+        \begin{itemize}
+            \item If I read a $0$ (there is no edge), I go right.
+            \item If I read a $1$ (there is an edge), I go down.
+        \end{itemize}
+
+        This takes $\pazocal O(|V|)$ time (at most $2|V|-2$ steps). The rationale is that the row that we are belongs to the vertex we're currently checking if it could be a sink. If we read a zero, the vertex we're checking doesn't have that particular outgoing edge, so we stay in the same row. If we read a one, the vertex does have an outgoing edge, so we can go to the next one. 
+
+        However, we don't check all edges for every vertex (that would require $\pazocal O(|V|^2)$ time). Therefore, in the final position we need to check that the row we are in is all-zero, and that the corresponding column has all-one (except on the diagonal) -- i.e., we need to verify that the vertex we end up in actually is a sink. This is also $\pazocal O(|V|)$.
 
     \item \begin{enumerate}
             \item \begin{proof}
                 Suppose without loss of generality that we colour $v_1$ blue. Then $v_2$ must be red, $v_3$ blue, and in general every $v_i$ with odd $i$ is blue and every $v_j$ with even $j$ red. Then $v_k$ must be blue. However, then $c(v_1)=c(v_k)$ while $(v_k,v_1)\in E$. This is in contradiction with the definition of a 2-colouring. Hence, there exists no 2-colouring in a graph with an odd-length cycle.
                 \end{proof}
 
-            \item We apply BFS and colour every odd-distance vertex blue, while we colour every even-distance vertex red. %todo proof
+            \item We apply BFS and colour every odd-distance vertex blue, while we colour every even-distance vertex red. 
+
+                \begin{proof}
+                    Suppose now there are two adjacent vertices $v_1,v_2$ with the same colour. Then say without loss of generality this is blue (and thus that they both have odd-distance to the root $r$). Then their distance to the root must be the same, because if the distances are $d,d+2k$ for some $k\in\mathbb N^+$, the distance $d+2k$ cannot be minimal: there is a shorter path from the root, through the other vertex, with length $d+1$.
+
+                    Then if the distance to the root is the same and there is an edge in between, there is a cycle $(r,\dots,v_1,v_2,\dots,r)$. This cycle has length $d+d+1$ which is odd. But this is in contradiction with the assumption there are no odd-length cycles.
+
+                    Therefore, there are no two adjacent vertices with the same colour, hence the colouring is correct.
+                \end{proof}
         \end{enumerate}
 
-    \item %todo
+    \item A possible way to write this down would be:
+
+        \begin{enumerate}[label=\arabic*)]
+            \item Let $S:=[]$, and compute $Q$ as all vertices without incoming edges.
+            \item Take a vertex $v$ from $Q$, and add it to the tail of $S$.
+            \item For every node $(v,v')$, remove it from the graph, and add $v'$ to $Q$ if it has no other incoming edges.
+            \item If $Q$ is non-empty, go back to 2) -- otherwise, terminate.
+        \end{enumerate}
+        
+        \begin{proof}
+            A vertex with in-degree zero is (one of) the first vertex(ices) of the graph in topological order. Furthermore, there is always such a vertex, because otherwise there is a cycle (or $V=\emptyset$). Then by induction it follows that the same holds for every subgraph with the edges of that vertex with in-degree zero removed. Therefore, the algorithm is correct.
+        \end{proof}
 \end{enumerate}
 
 \end{multicols}