In this Bachelor degree thesis, we study random graphs. We focus on two of the most common models of random graphs, which we call the uniform model of random graphs and the binomial model of random graphs.
In the uniform model randomness is expressed via the decision of which m edges will be chosen from the set of all possible edges, that a graph on n nodes can have. On the other hand, in the binomial model randomness is expressed in such a way, that we perform a Bernoulli experiment with probability p for each possible edge, where the experiment's output determines whether or not the edge will be present in the graph. We calculate mathematical expectations for different properties in graphs for both models such as: the number of k-cycles in the graph, the number of isolated nodes, the number of complete subgraphs of given orders, etc. In order to get a better understanding of random graphs we present concrete examples and results of various computer simulations, enabling us to find “statistical probabilities” for certain properties to occur in a random graph.
|
