Spin System (pairwise Markov random field) instance: ·undirected G(V,E); Ad ·q states:[q]; each edge eEE associated with an activity: a symmetric nonnegative gxg matrix Ae:[gl×[gl→R≥o each vertex veV associated with an external field: a nonnegative q-vector F:gR> goal:computing the partition function: Z=ΠAe(cu,x）ΠF(c) c∈[glVe=uw∈E v∈VSpin System (pairwise Markov random field) • undirected G(V,E); • q states: [q]; • each edge e∈E associated with an activity: • each vertex v∈V associated with an external field: Ae : [q] ⇥ [q] ! R￾0 a symmetric nonnegative q×q matrix a nonnegative q-vector Fv : [q] ! R￾0 instance: Z = X x2[q]V Y e=uv2E Ae(xu, xv) Y v2V Fv(xv) goal: computing the partition function: Aa Ab Ac Ad Ae Af Fw Fu Fv Fy Fx