Slučajni grafi

diplomsko delo

Matej Mencin (Author), Primož Šparl (Mentor)

Abstract

V diplomskem delu obravnavamo slučajne grafe. Pri tem predstavimo dva najbolj splošna modela slučajnih grafov, ki jih v diplomskem delu imenujemo enakomerni model slučajnega grafa in binomski model slučajnega grafa. V enakomernem modelu slučajnega grafa se slučajnost izraža pri odločitvi, katerih m povezav bomo izbrali iz množice vseh možnih povezav, ki jih ima lahko graf na n vozliščih. Po drugi strani se pri binomskem modelu slučajnega grafa slučajnost izraža tako, da za vsako možno povezavo v grafu izvedemo Bernoullijev eksperiment z verjetnostjo p, kjer nam izid eksperimenta določi, ali bomo to povezavo v graf vzeli ali ne. Za oba modela izračunamo in prikažemo rezultate za matematična upanja za različne lastnosti v grafih, kot so: število k-ciklov v grafu, število izoliranih vozlišč, število polnih podgrafov dane velikosti itd. Z namenom dobiti boljšo predstavo o slučajnih grafih, si pogledamo številne konkretne zglede in rezultate računalniških simulacij, iz katerih lahko razberemo »statistične verjetnosti«, da se v slučajnem grafu pojavijo določene lastnosti.

Keywords

verjetnost;kombinatorika;teorija grafov;

Data

Language:	Slovenian
Year of publishing:	2017
Typology:	2.11 - Undergraduate Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[M. Mencin]
UDC:	51(043.2)
COBISS:	11695689
Views:	872
Downloads:	181
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Random graphs
Secondary abstract:	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.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Ljubljani, Pedagoška fak., Dvopredmetni učitelj
Pages:	33 str.
ID:	10864172