= Solution
The <constraint hypergraph> has one <vertex> for each of $X_1,\ldots,X_9$ and one <hypergraph edge> for each constraint scope:
$$
\boxed{E_1=\{1,2,4\},\ E_2=\{2,3,5\},\ E_3=\{4,5,6\},\ E_4=\{6,7,8\},\ E_5=\{1,4,9\}.}
$$
Here $i$ abbreviates $X_i$. These five scopes follow the corrected source.<Intelligent Systems examination paper by the University of Oxford (2015)>[Printed p. 4, corrected Question 3(b), constraints (1)–(5)]{ref} The diagram uses the incidence representation: round nodes are the original <variables>, square nodes represent <hypergraph edges>, and a joining line means that the <variable> belongs to that constraint scope. The square nodes are not extra <variables> of $P$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/intelligent-systems-2015-hypergraph.png]
{title=Incidence drawing of the five constraint scopes in Question 3(b)}
In particular, the central pattern involving $X_2,X_4,X_5$ forms a cycle through three constraint scopes; the scopes cannot themselves simply be joined into a valid <tree decomposition> without an additional bag.
Back to article page
