Slučajni grafi

diplomsko delo

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

Povzetek

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.

Ključne besede

verjetnost;kombinatorika;teorija grafov;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2017
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[M. Mencin]
UDK:	51(043.2)
COBISS:	11695689
Št. ogledov:	872
Št. prenosov:	181
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Random graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Pedagoška fak., Dvopredmetni učitelj
Strani:	33 str.
ID:	10864172