Consider an undirected graph G = (VG, EG). A label cover problem with unique constraints associates each vertex of the graph with one of k labels {1, . . . , k} and each edge (i, j), with i < j, of the graph with a k-element permutation i,j , i.e., i,j : {1, . . . , k} {1, . . . , k} is one to one and onto. A labeling is valid if the label for vertex j, denoted vj , is equal to i,j (vi), where vi is the label for vertex i. 1. Explain how to construct the uniform probability distribution, p, over valid k-labelings of G with given 0 s using random variables that take values in the set {1, . . . , k} to represent possible labelings of the vertices of G. 2. For a given graph G, what does the MRF for your previous probability distribution look like? 3. Explain why your construction may not always yield a valid probability distribution for every choice of an integer k > 0 and every choice of 0 s. 4. Let G be the graph consisting of a single cycle on four nodes. What is the partition function (normalizing constant) of the MRF for this choice of G when k = 3 such that the permutation on each edge (i, j) with i < j has (1) = 2, (2) = 1, and (3) = 3?