diplomsko delo
Marko Pasterk (Avtor), Simon Špacapan (Mentor)

Povzetek

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 ne odvisnostno š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 pod graf v grafu G^p.

Ključne besede

matematika;slučajni grafi;matematično upanje;Markova neenakost;verjetnostni model;pragovna funkcija;drugi moment;metoda;diplomska dela;

Podatki

Jezik: Slovenski jezik
Leto izida:
Izvor: Maribor
Tipologija: 2.11 - Diplomsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [M. Pasterk]
UDK: 51(043.2)
COBISS: 19136264 Povezava se bo odprla v novem oknu
Št. ogledov: 1562
Št. prenosov: 145
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: RANDOM GRAPHS
Sekundarni povzetek: 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.
Sekundarne ključne besede: random graph;expectation;Markov’s inequality;probability model;threshold function;second moment method;
URN: URN:SI:UM:
Vrsta dela (COBISS): Diplomsko delo
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: 27 f.
Ključne besede (UDK): mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID: 19935
Priporočena dela:
, diplomsko delo
, Seminar on algebraic combinatorics, Ben-Gurion University of the Negev, Beer Sheva, Israel, June 25, 2008
, Visiting Assistant Professor, 1.10.-31.12.2008, Ohio State University, Columbus, Ohio, USA
, študijsko gradivo
, Seminar on Finite Geometry, Eötvös University, Budapest, Hungary, Sept. 23, 2005