1.1 --- a/exercises/solutions/sol05.tex	Sat Jun 09 23:45:57 2012 +0200
     1.2 +++ b/exercises/solutions/sol05.tex	Sun Jun 10 05:35:08 2012 +0200
     1.3 @@ -30,9 +30,9 @@
     1.4  \maketitle
     1.5  %
     1.6  \section*{Exercise 5.1}
     1.7 -(a) The following table shows the states during the iterations.\\\\
     1.8 +(a) The following table shows the states during the AC3 iterations.\\\\
     1.9  \begin{tabular}{r l l l}
    1.10 -Iteration & Queue & Revise & Domains\\\hline
    1.11 +Iteration & Queue & Revise & Domains\\\hline\\
    1.12        $0$ & $\{(v_1,v_2),(v_2,v_1),
    1.13                 (v_2,v_3),(v_3,v_2),
    1.14                 (v_1,v_3),(v_3,v_1)\}$
    1.15 @@ -81,5 +81,73 @@
    1.16            & $(\{1,2\},
    1.17                \{1,2\},
    1.18                \{1,2\})$\\
    1.19 +\end{tabular}\\\\\\
    1.20 +(b) The following table shows the states during the PC2 iterations.\\\\
    1.21 +\begin{tabular}{r l l l l l}
    1.22 +  Iteration & Queue & Revise-3 & $R_{v_1,v_2}$ & $R_{v_2,v_3}$ & $R_{v_1,v_3}$\\
    1.23 +  \hline\\
    1.24 +      $0$ & $\{(1,3,2),(1,2,3),(2,1,3)\}$
    1.25 +          & $ $ 
    1.26 +          & $\{(1,2),(2,1)\}$
    1.27 +          & $\{(1,1),(1,2),(2,1)\}$
    1.28 +          & $\{(1,1),(1,2),(1,3),$\\
    1.29 +      &&&&& $(1,4),(1,5),(2,2),$\\
    1.30 +      &&&&& $(2,3),(2,4),(2,5),$\\
    1.31 +      &&&&& $(3,3),(3,4),(3,5),$\\
    1.32 +      &&&&& $(4,4),(4,5),(5,5)\}$\\
    1.33 +      $1$ & $\{(1,3,2),(1,2,3)\}$
    1.34 +          & $(\{v_2,v_1\},v_3)$ 
    1.35 +          & $\{(1,2),(2,1)\}$
    1.36 +          & $\{(1,1),(1,2),(2,1)\}$
    1.37 +          & $\{(1,1),(1,2),(1,3),$\\
    1.38 +      &&&&& $(1,4),(1,5),(2,2),$\\
    1.39 +      &&&&& $(2,3),(2,4),(2,5),$\\
    1.40 +      &&&&& $(3,3),(3,4),(3,5),$\\
    1.41 +      &&&&& $(4,4),(4,5),(5,5)\}$\\
    1.42 +      $2$ & $\{(1,3,2)\}$
    1.43 +          & $(\{v_1,v_2\},v_3)$ 
    1.44 +          & $\{(1,2),(2,1)\}$
    1.45 +          & $\{(1,1),(1,2),(2,1)\}$
    1.46 +          & $\{(1,1),(1,2),(1,3),$\\
    1.47 +      &&&&& $(1,4),(1,5),(2,2),$\\
    1.48 +      &&&&& $(2,3),(2,4),(2,5),$\\
    1.49 +      &&&&& $(3,3),(3,4),(3,5),$\\
    1.50 +      &&&&& $(4,4),(4,5),(5,5)\}$\\
    1.51 +  $3$ & $\{\}\cup\{(2,1,3),(2,3,1)\}$
    1.52 +          & $(\{v_1,v_3\},v_2)$ 
    1.53 +          & $\{(1,2),(2,1)\}$
    1.54 +          & $\{(1,1),(1,2),(2,1)\}$
    1.55 +          & $\{(1,1),(2,2)\}$\\
    1.56 +  $4$ & $\{(2,1,3)\}\cup\{(1,2,3),(1,3,2)\}$
    1.57 +          & $(\{v_2,v_3\},v_1)$ 
    1.58 +          & $\{(1,2),(2,1)\}$
    1.59 +          & $\{(1,2),(2,1)\}$
    1.60 +          & $\{(1,1),(2,2)\}$\\
    1.61 +  $5$ & $\{(2,1,3),(1,2,3)\}$
    1.62 +          & $(\{v_1,v_3\},v_2)$ 
    1.63 +          & $\{(1,2),(2,1)\}$
    1.64 +          & $\{(1,2),(2,1)\}$
    1.65 +          & $\{(1,1),(2,2)\}$\\
    1.66 +  $6$ & $\{(2,1,3)\}$
    1.67 +          & $(\{v_1,v_2\},v_3)$ 
    1.68 +          & $\{(1,2),(2,1)\}$
    1.69 +          & $\{(1,2),(2,1)\}$
    1.70 +          & $\{(1,1),(2,2)\}$\\
    1.71 +  $7$ & $\{\}$
    1.72 +          & $(\{v_2,v_1\},v_3)$ 
    1.73 +          & $\{(1,2),(2,1)\}$
    1.74 +          & $\{(1,2),(2,1)\}$
    1.75 +          & $\{(1,1),(2,2)\}$
    1.76  \end{tabular}
    1.77 +
    1.78 +\section*{Exercise 5.3}
    1.79 +(a) In a path-consistent network for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$.
    1.80 +
    1.81 +Since all the $R_{ij}$ are non-empty and all our variables $v_i$ share the same domain values, it follows that all $v_i$ are arc-consistent relative to $v_k$ and all $v_k$ are arc-consistent relative to $v_j$, which induces that all $R_{ij}$ are arc-consistent, since otherwise they would be no $a_i\in D_i$, such that $(a_k,a_i)\in R_{ki}$ and $(a_i,a_j)\in R_{ij}$. \qed\\\\
    1.82 +(b) We know that all sets $A_m\subseteq\{0,1\}$ are non-empty, i.e., $1\leq|A_m|\leq2$ for all $1\leq m\leq l$. Therefore it holds that the intersection of two sets $A_q=A_o\cap A_p$ has cardinality $0\leq|A_q|\leq \min\{|A_o|,|A_p|\}\leq 2$.
    1.83 +
    1.84 +WLOG, we know that $A_q$ becomes the empty set, iff $A_o=\{0\}$ and $A_p=\{1\}$ and any combination of $A_o=\{0,1\}$ and $A_p\subset A_o$ yields the set $A_q=A_p$. Therefore it holds that for $\bigcap_{1\leq m\leq l}{A_m}=\emptyset$ to hold, there must be two sets holding the distinct elements $0$ and $1$ respectively, as has been shown. \qed\\\\
    1.85 +(c) We prove by contradiction. Assume that the partial assignment on $v_1,...,v_{k-1}$ can not be extended to $v_k$, i.e., $\bigcap_{2\leq i\leq k-1}{\{a_k\mid (a_i,a_k)\in R_{ik}\}}=\emptyset$. By (b) follows that there must be $2\leq i\neq j\leq k-1$, such that $\{a_k\mid(a_i,a_k)\in R_{ik}\}\cap\{a_k\mid(a_j,a_k)\in R_{jk}\}=\emptyset$.
    1.86 +
    1.87 +WLOG let $\{a_k\mid(a_i,a_k)\in R_{ik}\}=\{0\}$ and $\{a_k\mid(a_j,a_k)\in R_{jk}\}=\{1\}$. We know that we have non-empty constraints on all variable pairs $R_{ij}$ and there is a consistent assignment $(a_i,a_j)\in R_{ij}$. By our assumption there is an assignement $(a_i,0)\in R_{ik}$ but no $(a_j,0)\in R_{jk}$. This contradicts to the definition of path-consistency, where for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$. Therefore there can not be such an assumption in a path-consistent network with given properties and we can extend the assignment to $v_k$. \qed
    1.88  \end{document}