Problem

In this question, we study how we can define a cluster graph for a Bayesian network.

a. Consider the following two schemes for converting a Bayesian network structure G to a cluster graph U. For each of these two schemes, either show (by proving the necessary properties) that it produces a valid cluster graph for a general Bayesian network, or disprove this result by showing a counterexample.

• Scheme 1: For each node X_iin G, define a cluster C_iover X_i's family. Connect C_iand C_jif X_jis a parent of X_iin G, and define the sepset to be the intersection of the clusters.
• Scheme 2: For each node X_iin G, define a cluster C_iover X_i's family. Connect C_iand C_jif X_jis a parent of X_iin G, and define the sepset to be the {X_j}.

b. Construct an alternative scheme to the ones proposed earlier that uses a minimum spanning tree algorithm to transform any Bayesian network into a valid cluster graph.