Why is the most probable assignment for all variables in MRFs called MAP assignment?
MLE is a point estimate $\hat{\theta}_{\text{MLE}}$ that resides at a mode of the likelihood density. That is,
$$L(\theta; X) = \Pr(X | \theta)\\
\hat{\theta}_{\text{MLE}} = \arg \max_{\theta} \Pr(X | \theta)$$

MAP stands for maximum a-posteriori. It is a point estimate $\hat{\theta}_{\text{MAP}}$ that resides at a mode of the posterior distribution (the distribution over the parameters themselves conditioned on our observed data). We can perform MAP estimation by incorporating a prior distribution for our parameters.

$$ \Pr(\theta | X) = \frac{\Pr(X | \theta) \Pr(\theta)}{\Pr(X)} \\
\Pr(\theta | X) \propto \Pr(X | \theta) \Pr(\theta) \\ 
\hat{\theta}_{\text{MAP}} = \arg \max_{\theta} \Pr(X |\theta)\Pr(\theta)$$

This is a simple application of Bayes' Theorem. The reason we use "proportional to" is that we don't care about the marginal likelihood constant. Since it is only a constant our point estimate for this "psuedo-MAP" still corresponds to a point-estimate for the true MAP. By definition $\hat{\theta}_{\text{MAP}}$ is the (at least locally) most-probable estimate under the posterior distribution.

The key take-away is that the Maximum Likelihood estimate is the point estimate that maximizes the probability of observing your data. The MAP estimate is the point estimate that is the (at least locally) most probable under your posterior distribution of parameters. In the end deciding whether to use the MLE or MAP estimate is up to you and your model. It really depends on what you are more interested in. 

To stress the difference one last time, look at the difference between the two definitions for the distributions being maximized over. In ML estimation we are maximizing over the distribution of observing our data; in MAP estimation we are maximizing over the distribution of parameters themselves. Hence why we can say MAP estimates are the most-probable estimate whereas we cannot for the ML estimate.