This paper first presents the basic concepts of random graph theory, including undirected, directed, and generalized random graphs. A random homomorphic number mapping is introduced to solve the cut distance problem of directed random graphs, and a minimum cut distance is proposed. Next, a virtual machine deployment strategy (VMDS) based on the minimum cut algorithm is proposed to construct VM clusters based on similarity and to cut VM clusters based on the minimum cut of directed random graphs. According to the results, the MAE (1.3875) and MSE (2.7783) of both the conventional AR algorithm and ES algorithm are the lowest. Compared to the MAE (1.7381) and MSE (3.7840) of the VMDS algorithm, both significantly decrease. The research results presented in this paper are useful for applying virtual machine deployment techniques in cloud computing.