Junfeng Qu

"Simulation of Random Maximal Circuits in Complete Graphs"

Abstract:

Simulation has been increasingly used for the solution of problems in business, engineering, physical sciences, and social sciences. Simulation is valuable both for its relative simplicity and for its potential to study a large number of variants of the original model without incurring the costs associated with physical experimentation or facing the difficulties of re-deriving formulas for output parameters that are inherent in mathematical analysis. For an arbitrary graph G, finding the largest eulerian subgraph of odd order is an NP-complete problem. The asymptotic behavior of the number of eulerian circuits in a complete graph of odd order had been studied, and the probability that all the edges are eventually used in a random maximal circuit has been shown to be asymptotic to e^3/4n^-1/2. However the probabilities for cases in which not all the edges are used remain unknown because of the complexity of the analysis. This thesis is a pilot study of all the cases of random maximal circuits on the complete graphs of odd order by computer simulation. The simulation estimates of the probability that all edges are used conform very closely to the asymptotic value. The probability that three edges are left after the random maximal circuit appears also to be O(n^-1/2), but this pattern is not observed when 4 or more edges are left. The smaller the number of edges left after the random maximal circuit, the more likely the outcome is to occur. The left over edges tend to form a connected subgraph.