\documentclass[10pt,a4paper]{article}

\usepackage[margin=2cm]{geometry}
\usepackage{multicol}

\usepackage{enumitem}
\setenumerate[1]{label=4.\arabic*.}
\setenumerate[2]{label=\textit{\alph*})}

\usepackage{hhline}

% textcomp package is not available everywhere, and we only need the Copyright symbol
% taken from http://tex.stackexchange.com/a/1677/23992
\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}

\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\fancyhead{}
\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
\pagestyle{fancy}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}

\usepackage{minted}

\usepackage{tikz}

\parindent0pt

\title{Algoritmen en Datastructuren - assignment 4}
\author{Camil Staps\\\small{s4498062}}

\tikzstyle{gray}=[fill=gray!20]
\tikzstyle{black}=[fill=gray!60]
\tikzstyle{active}=[draw=red]

\begin{document}

\maketitle
\thispagestyle{fancy}

\begin{multicols}{2}

\begin{enumerate}
    \item \begin{enumerate}
            \item See the figures below:\\[2pt]
                
                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node (A) {$A$};
                        \node[right of=A] (B) {$B$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[above of=A] (E) {$E$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[active,gray] (A) {$0$};
                        \node[right of=A] (B) {$B$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[above of=A] (E) {$E$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[active,black] (A) {$0$};
                        \node[active,gray,right of=A] (B) {$1$};
                        \node[right of=B] (C) {$C$};
                        \node[right of=C] (D) {$D$};
                        \node[active,gray,above of=A] (E) {$1$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[active,black,right of=A] (B) {$1$};
                        \node[active,gray,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[gray,above of=A] (E) {$1$};
                        \node[right of=E] (F) {$F$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[gray,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[active,black,above of=A] (E) {$1$};
                        \node[active,gray,right of=E] (F) {$2$};
                        \node[right of=F] (G) {$G$};
                        \node[right of=G] (H) {$H$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[active,black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[gray,right of=E] (F) {$2$};
                        \node[active,gray,right of=F] (G) {$3$};
                        \node[active,gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[active,black,right of=E] (F) {$2$};
                        \node[gray,right of=F] (G) {$3$};
                        \node[gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[right of=C] (D) {$D$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[active,black,right of=F] (G) {$3$};
                        \node[gray,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[active,gray,right of=C] (D) {$4$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[black,right of=F] (G) {$3$};
                        \node[active,black,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node[black] (A) {$0$};
                        \node[black,right of=A] (B) {$1$};
                        \node[black,right of=B] (C) {$2$};
                        \node[active,black,right of=C] (D) {$4$};
                        \node[black,above of=A] (E) {$1$};
                        \node[black,right of=E] (F) {$2$};
                        \node[black,right of=F] (G) {$3$};
                        \node[black,right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (B); \draw (E) -- (F);
                        \draw (F) -- (B); \draw (F) -- (G);
                        \draw (G) -- (B); \draw (G) -- (H);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

                The BFS tree is then:\\[2pt]
                
                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,node distance=15mm,every node/.style={shape=circle,draw,font=\scriptsize}]
                        \node (A) {$0$};
                        \node[right of=A] (B) {$1$};
                        \node[right of=B] (C) {$2$};
                        \node[right of=C] (D) {$4$};
                        \node[above of=A] (E) {$1$};
                        \node[right of=E] (F) {$2$};
                        \node[right of=F] (G) {$3$};
                        \node[right of=G] (H) {$3$};
                        \draw (A) -- (E); \draw (A) -- (B);
                        \draw (B) -- (C);
                        \draw (C) -- (G); \draw (C) -- (H);
                        \draw (E) -- (F);
                        \draw (H) -- (D);
                    \end{tikzpicture}
                \end{minipage}\\

            \item This gives:\\[2pt]

                \begin{minipage}[b]{\linewidth}
                    \centering
                    \begin{tikzpicture}[->,level 1/.style={sibling distance=20mm},level 2/.style={sibling distance=15mm},node distance=15mm,every node/.style={shape=circle,draw,font=\tiny,align=center}]
                        \node {$A$\\$1/16$}
                            child { node {$B$\\$2/11$}
                                child { node {$C$\\$3/10$}
                                    child { node {$G$\\$4/9$}
                                        child { node {$H$\\$5/8$}
                                            child { node {$D$\\$6/7$} }
                                        }
                                        child { node[gray] {$B$} }
                                    }
                                    child { node[gray] {$H$} }
                                }
                            }
                            child { node {$E$\\$12/15$} 
                                child { node[gray] {$B$} }
                                child { node {$F$\\$13/14$}
                                    child { node[gray] {$B$} }
                                        child { node[gray] {$G$} }
                                }
                            };
                    \end{tikzpicture}
                \end{minipage}
        \end{enumerate}

    \item \begin{enumerate}[label=\arabic*)]
            \item Compute $\{(v,degree[v]) \mid v\in V\}$; this can be done in $\pazocal O(|V|+|E|)$.
            \item Using those vertex-degree pairs, compute for every vertex the sum of the degrees of its neighbours: also this is simply looping the vertices and their edges and can therefore be done in $\pazocal O(|V|+|E|)$.
        \end{enumerate}

        Since both parts of the algorithm are $\pazocal O(|V|+|E|)$, the whole algorithm is that as well.

    \item \begin{enumerate}[label=\arabic*)]
            \item Let $A = \emptyset$, $Q := \{(r,\emptyset)\}$.
            \item Choose a $(v,P)\in Q$, and remove it from the queue.
            \item For every child $c$ of $v$, add $(v',c)$ to $A$ for all $v'\in P\cup\{v\}$. Then, add $(c, P\cup\{v\})$ to $Q$.
            \item If $Q\neq\emptyset$, go back to 2.
        \end{enumerate}

        We keep a queue $Q$ of nodes $v$ that we have to check still and their ancestors $P$. Then for every child $c$ of a node $v$ in $Q$, we add $(c,v')$ to the list of child-ancestor pairs that is $A$. 

        We only visit every edge once, so this is done in linear time. 

    \item %todo

    \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
        \end{enumerate}

    \item %todo
\end{enumerate}

\end{multicols}

\end{document}

