aboutsummaryrefslogtreecommitdiff
path: root/assignment4.tex
diff options
context:
space:
mode:
Diffstat (limited to 'assignment4.tex')
-rw-r--r--assignment4.tex345
1 files changed, 345 insertions, 0 deletions
diff --git a/assignment4.tex b/assignment4.tex
new file mode 100644
index 0000000..d478b7d
--- /dev/null
+++ b/assignment4.tex
@@ -0,0 +1,345 @@
+\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}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-16 22:51:24 +0000