The MRF is defined over the image domain and is merely a graph structure, that can be partitioned with several algorithms (very popular is the alpha-expansion method: Y.Boykov et al. "Fast approximate energy minimization via graph cuts" PAMI 2001.). Effectively you define a cost function, incorporating information about the regions to be segmented, such as intensity information, shape, region order etc and apply it to the connections of the source to each node (representing a pixel/voxel in the image) and a separate cost for the capacity of the connections between nodes (ie. edges). The algorithm then often calculates a maximum flow through the graph, which is equivalent to a minimum cut (according to the energy functional defined by the different cost functions), that represents your segmentation result.
This is of course very condensed information and you should read up on it. I would suggest you read up on max-flow/min-cut and different solvers (Ford-Fulkerson, alpha-expansion, or continuous max-flow (binary implementation at http://www.mathworks.com/matlabcentral/fileexchange/34126-fast-continuous-max-flow-algorithm-to-2d3d-image-segmentation).