SLUČAJNI GRAFIPasterk, Marko (Avtor) Špacapan, Simon (Mentor) slučajni grafmatematično upanjeMarkova neenakostverjetnostni modelpragovna funkcijametoda drugega momentaDiplomsko 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. [M. Pasterk]20122012-04-18 20:57:18Diplomsko delo22739UDK: 51(043.2)COBISS_ID: 19136264NUK URN: URN:SI:UM:DK:S9KBG4YVsl