sawine@5
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@5
|
2 |
\usepackage{graphicx}
|
sawine@5
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@5
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@5
|
5 |
\usepackage{typearea}
|
sawine@5
|
6 |
\usepackage{algorithm}
|
sawine@5
|
7 |
\usepackage{algorithmic}
|
sawine@5
|
8 |
\usepackage{fullpage}
|
sawine@5
|
9 |
\usepackage{mathtools}
|
sawine@5
|
10 |
\usepackage[all]{xy}
|
sawine@5
|
11 |
\addtolength{\voffset}{-40pt}
|
sawine@5
|
12 |
\title{CSP Exercise 02 Solution}
|
sawine@5
|
13 |
\author{Eugen Sawin}
|
sawine@5
|
14 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@5
|
15 |
\newcommand{\E}{\mathcal{E}}
|
sawine@5
|
16 |
\newcommand{\R}{\mathcal{R}}
|
sawine@5
|
17 |
|
sawine@5
|
18 |
%\include{pythonlisting}
|
sawine@5
|
19 |
|
sawine@5
|
20 |
\pagestyle{empty}
|
sawine@5
|
21 |
\begin{document}
|
sawine@5
|
22 |
\maketitle
|
sawine@5
|
23 |
|
sawine@5
|
24 |
\section*{Exercise 2.1}
|
sawine@5
|
25 |
(a) The strongly connected components are the subgraphs induced by following sets of vertices.
|
sawine@5
|
26 |
\begin{itemize}
|
sawine@5
|
27 |
\item $V_1 = \{v_1,v_2,v_5,v_6\}$
|
sawine@5
|
28 |
\item $V_2 = \{v_3,v_4\}$
|
sawine@5
|
29 |
\end{itemize}
|
sawine@5
|
30 |
(b) The cliques are the the complete subgraphs induced by the following sets of vertices.
|
sawine@5
|
31 |
\begin{itemize}
|
sawine@5
|
32 |
\item $V_1 = \{v_1,v_2,v_5\}$
|
sawine@5
|
33 |
\item $V_{2-8} \in E$
|
sawine@5
|
34 |
\item $V_{9-14} \in \{\{v_i\} \mid v_i \in V\}$
|
sawine@5
|
35 |
\end{itemize}
|
sawine@5
|
36 |
|
sawine@5
|
37 |
\section*{Exercise 2.2}
|
sawine@5
|
38 |
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.
|
sawine@5
|
39 |
\begin{enumerate}
|
sawine@5
|
40 |
\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$.
|
sawine@5
|
41 |
\item If $F = W$ terminate, we have found a solution.\\
|
sawine@5
|
42 |
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\}$.\\
|
sawine@5
|
43 |
Add all its disliked neighbours to $B_2$, i.e. $B_2 = B_2 \cup \{w_j \mid \{w_i,w_j\} \in E\}$.\\
|
sawine@5
|
44 |
If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.
|
sawine@5
|
45 |
\item If there a $w_i \notin F$ with $w_i \in B_1 \cup B_2$ select it, otherwise continue with $2.$\\
|
sawine@5
|
46 |
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\}$.\\
|
sawine@5
|
47 |
If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
|
sawine@5
|
48 |
Otherwise continue with $3.$
|
sawine@5
|
49 |
\end{enumerate}
|
sawine@5
|
50 |
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|)$.
|
sawine@5
|
51 |
\end{document}
|