20.500.12556/DKUM-22739 SLUČAJNI GRAFI RANDOM GRAPHS Diplomsko delo obravnava slučajne grafe. Osrednja tema so lastnosti, ki veljajo za skoraj vse grafe. V uvodnem delu so podane definicije iz verjetnosti in teorije grafov, ki jih potrebujemo v nadaljevanju diplomskega dela. V prvem poglavju s pomočjo matematičnega upanja določimo eno zgornjo in eno spodnjo mejo za dominantno število in neodvisnostno število grafa. Prav tako dokažemo obstoj grafa z velikim kromatičnim številom in velikim notranjim obsegom. V drugem poglavju sta predstavljena dva verjetnostna modela, s katerima opišemo lastnosti skoraj vseh grafov. Nekaj teh lastnosti tudi dokažemo. V zadnjem poglavju definiramo pragovne funkcije in določimo prag za lastnost obstoja izoliranih vozlišč v grafu G^p in za lastnost obstoja fiksnega grafa H kot podgraf v grafu G^p. The graduation thesis focuses on random graphs, in particular, we study properties of almost all graphs. In the introductory section definitions on probability theory and graph theory are given. In first chapter we use expectation to determine upper and lower bound for the domination number and the independence number of graph. We also prove the existence of graphs with large chromatic number and large girth. In second chapter there are presented two probability models that give us a way to describe properties of almost all graphs. In the last chapter we define threshold functions and determine the threshold for disappearance of isolated vertices in graph G^p and for appearance of isolated vertices of a fixed graph H as a subgraph of G^p. slučajni graf matematično upanje Markova neenakost verjetnostni model pragovna funkcija metoda drugega momenta random graph expectation Markov’s inequality probability model threshold function second moment method true true false [M. Pasterk] Slovenski jezik Angleški jezik Diplomsko delo 2012-04-18 20:57:18 2012-05-17 13:15:50 2022-04-14 12:03:50 2023-12-30 03:15:35 2012 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 19136264 URN:SI:UM:DK:S9KBG4YV UNI_Pasterk_Marko_2012.pdf UNI_Pasterk_Marko_2012.pdf 1 9695C06BF220B7BD9DC45DE498B995D6 ae1031b27014f9e9bc0aa57ef8ee9f1f5f97d5df0b9c00d1fcbb096bcb1294c2 90352d11-7c06-11eb-bb7a-00155d0001ca 20.500.12556/dkum/d8d33769-bed3-44d6-b0ba-d061556733cc https://dk.um.si/Dokument.php?lang=slv&id=29497 Fakulteta za naravoslovje in matematiko 0 0 0