# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1339299308 -7200
# Node ID 93fd38efa60f7b4774c92c6d3996ce98a5f346c1
# Parent  9f72ba296485f3933e34fe2d5f9458acd5ef411a
Added some solutions.

diff -r 9f72ba296485 -r 93fd38efa60f exercises/solutions/sol05.tex
--- a/exercises/solutions/sol05.tex	Sat Jun 09 23:45:57 2012 +0200
+++ b/exercises/solutions/sol05.tex	Sun Jun 10 05:35:08 2012 +0200
@@ -30,9 +30,9 @@
 \maketitle
 %
 \section*{Exercise 5.1}
-(a) The following table shows the states during the iterations.\\\\
+(a) The following table shows the states during the AC3 iterations.\\\\
 \begin{tabular}{r l l l}
-Iteration & Queue & Revise & Domains\\\hline
+Iteration & Queue & Revise & Domains\\\hline\\
       $0$ & $\{(v_1,v_2),(v_2,v_1),
                (v_2,v_3),(v_3,v_2),
                (v_1,v_3),(v_3,v_1)\}$
@@ -81,5 +81,73 @@
           & $(\{1,2\},
               \{1,2\},
               \{1,2\})$\\
+\end{tabular}\\\\\\
+(b) The following table shows the states during the PC2 iterations.\\\\
+\begin{tabular}{r l l l l l}
+  Iteration & Queue & Revise-3 & $R_{v_1,v_2}$ & $R_{v_2,v_3}$ & $R_{v_1,v_3}$\\
+  \hline\\
+      $0$ & $\{(1,3,2),(1,2,3),(2,1,3)\}$
+          & $ $ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(1,3),$\\
+      &&&&& $(1,4),(1,5),(2,2),$\\
+      &&&&& $(2,3),(2,4),(2,5),$\\
+      &&&&& $(3,3),(3,4),(3,5),$\\
+      &&&&& $(4,4),(4,5),(5,5)\}$\\
+      $1$ & $\{(1,3,2),(1,2,3)\}$
+          & $(\{v_2,v_1\},v_3)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(1,3),$\\
+      &&&&& $(1,4),(1,5),(2,2),$\\
+      &&&&& $(2,3),(2,4),(2,5),$\\
+      &&&&& $(3,3),(3,4),(3,5),$\\
+      &&&&& $(4,4),(4,5),(5,5)\}$\\
+      $2$ & $\{(1,3,2)\}$
+          & $(\{v_1,v_2\},v_3)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(1,3),$\\
+      &&&&& $(1,4),(1,5),(2,2),$\\
+      &&&&& $(2,3),(2,4),(2,5),$\\
+      &&&&& $(3,3),(3,4),(3,5),$\\
+      &&&&& $(4,4),(4,5),(5,5)\}$\\
+  $3$ & $\{\}\cup\{(2,1,3),(2,3,1)\}$
+          & $(\{v_1,v_3\},v_2)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(1,2),(2,1)\}$
+          & $\{(1,1),(2,2)\}$\\
+  $4$ & $\{(2,1,3)\}\cup\{(1,2,3),(1,3,2)\}$
+          & $(\{v_2,v_3\},v_1)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(2,2)\}$\\
+  $5$ & $\{(2,1,3),(1,2,3)\}$
+          & $(\{v_1,v_3\},v_2)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(2,2)\}$\\
+  $6$ & $\{(2,1,3)\}$
+          & $(\{v_1,v_2\},v_3)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(2,2)\}$\\
+  $7$ & $\{\}$
+          & $(\{v_2,v_1\},v_3)$ 
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,2),(2,1)\}$
+          & $\{(1,1),(2,2)\}$
 \end{tabular}
+
+\section*{Exercise 5.3}
+(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}$.
+
+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\\\\
+(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$.
+
+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\\\\
+(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$.
+
+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
 \end{document}