Markov networks and Bayesian networks are two popular models for classification. Vapnik-Chervonenkis dimension and Euclidean dimension are two measures of complexity of a class of functions. We show that these two dimensional values of the concept class induced by a discrete Markov network are identical, and the value equals dimension of the toric ideal corresponding to this Markov network as long as the toric ideal is nontrivial. Furthermore, we provide a simple formula for calculating the dimensions of discrete Markov networks. For a general Bayesian network, we show that dimension of the corresponding toric ideal offers an upper bound of Euclidean dimension. Consider VC dimensions induced by the concept classes of a class of Bayesian networks, where each underlying graph is a cycle containing exactly one V-structure. We prove that the three quantities mentioned above for this kind of Bayesian networks are equal.