In the master's thesis, we discuss various topics from the theory of random graphs. Random graphs can be seen as graphs on a selected number of vertices, where the structure of the graph is not ‘‘fixed’’, but changes according to the selected probability for each possible edge, or according to the decision of how many edges are randomly selected from the set of all possible graph edges.
In the master's thesis we explore various basic properties of random graphs and consider the question of when a random graph has a certain graph property, such as being connected. We also present probabilistic methods in random graphs, which provide an important tool in mathematics for proving the existence of a certain object without ‘‘constructing’’ that object. At the same time, in the case of random graphs, we are also interested in the ‘‘problem’’ of small subgraphs, i.e. we consider the question of when a certain subgraph appears in a random graph, such as tree, cycle, complete graph, etc. At the end of the master's thesis we ask ourselves about the existence of a giant component in the graph and empirically present its development and the (already) known four phases of this development.
As there is not much literature currently available on this topic in Slovene, the main purpose of the master's thesis is to present the basics of the theory of random graphs to the reader in an understandable and simple way and, if possible, to arouse the reader's interest in further research. The work is an ‘‘overture’’ to the theory of random graphs, which is why we also discussed the basics of probability theory and graph theory, on which the theory of random graphs is based. As a supplement to the master's thesis, in the appendix, we also include a section on measure theory, which is needed for an axiomatic definition of probability.
|
