1.1 Binary file exercises/blatt02.pdf has changed

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/exercises/solutions/sol02.tex	Wed May 09 01:04:24 2012 +0200
     2.3 @@ -0,0 +1,51 @@
     2.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
     2.5 +\usepackage{graphicx}
     2.6 +%\usepackage[latin1]{inputenc}
     2.7 +\usepackage{amsmath, amsthm, amssymb}
     2.8 +\usepackage{typearea}
     2.9 +\usepackage{algorithm}
    2.10 +\usepackage{algorithmic}
    2.11 +\usepackage{fullpage}
    2.12 +\usepackage{mathtools}
    2.13 +\usepackage[all]{xy}
    2.14 +\addtolength{\voffset}{-40pt}
    2.15 +\title{CSP Exercise 02 Solution}
    2.16 +\author{Eugen Sawin}
    2.17 +\renewcommand{\familydefault}{\sfdefault}
    2.18 +\newcommand{\E}{\mathcal{E}}
    2.19 +\newcommand{\R}{\mathcal{R}}
    2.20 +
    2.21 +%\include{pythonlisting}
    2.22 +
    2.23 +\pagestyle{empty}
    2.24 +\begin{document}
    2.25 +\maketitle
    2.26 +
    2.27 +\section*{Exercise 2.1}
    2.28 +(a) The strongly connected components are the subgraphs induced by following sets of vertices.
    2.29 +\begin{itemize}
    2.30 +  \item $V_1 = \{v_1,v_2,v_5,v_6\}$
    2.31 +  \item $V_2 = \{v_3,v_4\}$
    2.32 +\end{itemize}
    2.33 +(b) The cliques are the the complete subgraphs induced by the following sets of vertices.
    2.34 +\begin{itemize}
    2.35 +  \item $V_1 = \{v_1,v_2,v_5\}$
    2.36 +  \item $V_{2-8} \in E$
    2.37 +  \item $V_{9-14} \in \{\{v_i\} \mid v_i \in V\}$
    2.38 +\end{itemize}
    2.39 +
    2.40 +\section*{Exercise 2.2}
    2.41 +We define the following undirected simple graph $G = \langle W, E \rangle$ with $\{w_i,w_j\} \in E$ iff $w_i$ and $w_j$ dislike each other. Additionally we define two sets $B_1 = B_2 = \{\}$ for the buildings and an auxiliary set $F = \{\}$ for remembering \emph{expanded} nodes.
    2.42 +\begin{enumerate}
    2.43 +  \item For all $w_i \in W$ with $w_i \notin \bigcup E$ add $w_i$ to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$. This way we assign all workers, who are liked by everyone to building $B_1$.
    2.44 +  \item If $F = W$ terminate, we have found a solution.\\
    2.45 +  Otherwise select any $w_i \notin F$ and add it to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$.\\
    2.46 +  Add all its disliked neighbours to $B_2$, i.e. $B_2 = B_2 \cup \{w_j \mid \{w_i,w_j\} \in E\}$.\\
    2.47 +  If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.
    2.48 +  \item If there a $w_i \notin F$ with $w_i \in B_1 \cup B_2$ select it, otherwise continue with $2.$\\
    2.49 +  Add all its disliked neighbours to the other building, i.e. $w_i \in B_1 \implies B_2 = B_2 \cup \{w_j \mid (w_i,w_j) \in E\}$, $w_i \in B_2 \implies B_1 = B_1 \cup \{w_j \mid (w_i,w_j) \in E\}$ and $F = F \cup \{w_i\}$.\\
    2.50 +  If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
    2.51 +  Otherwise continue with $3.$
    2.52 +\end{enumerate}
    2.53 +This is essentially a breadth-first search with random-walk used to jump to disconnected nodes. Assumming that set containment can be tested in $\mathcal{O}(1)$ and set intersection in $\mathcal{O}(n)$ we have an asymptotic complexity of $\mathcal{O}(|W| \cdot |E|)$.
    2.54 +\end{document}