.Example
a
Prompt
Question: Let G G be a graph. An edge-indicator of G G is a function a : { 0 , 1 } → V ( G ) a:{0,1}→V(G) such that { a ( 0 ) , a ( 1 ) } ∈ E ( G ) {a(0),a(1)}∈E(G). Consider the following Markov Chain M = M ( G ) M=M(G): The statespace of M M is the set of all edge-indicators of G G, and the transitions are defined as follows: Assume M t = a M t =a. 1. pick b ∈ { 0 , 1 } b∈{0,1} u.a.r. 2. pick v ∈ N ( a ( 1 − b ) ) v∈N(a(1−b)) u.a.r. (here N ( v ) N(v) denotes the open neighbourhood of v v) 3. set a ′ ( b ) = v a ′ (b)=v and a ′ ( 1 − b ) = a ( 1 − b ) a ′ (1−b)=a(1−b) 4. Set M t + 1 = a ′ M t+1 =a ′ We call a class of graphs G G well-behaved if, for each G ∈ G G∈G the Markov chain M ( G ) M(G) converges to a unique stationary distribution, and the unique stationary distribution is the uniform distribution. Which of the following graph classes is well-behaved? Answer Choices: A. The class of all non-bipartite regular graphs B. The class of all connected cubic graphs C. The class of all connected graphs D. The class of all connected non-bipartite graphs E. The class of all connected bipartite graphs.
