Slučajni grafi
diplomsko delo
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: | 2012 |
| 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
|
| Št. ogledov: | 1562 |
| Št. prenosov: | 145 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
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:
Slučajni grafi
2012,
diplomsko delo
Generalized Petersen graphs via algebraic graph theory
2008,
Seminar on algebraic combinatorics, Ben-Gurion University of the Negev, Beer Sheva, Israel, June 25, 2008
Math 568 - Linear Algebra
2008,
Visiting Assistant Professor, 1.10.-31.12.2008, Ohio State University, Columbus, Ohio, USA
Proklova hipopeda
2013,
študijsko gradivo
On nonexistence of semiovals
2005,
Seminar on Finite Geometry, Eötvös University, Budapest, Hungary, Sept. 23, 2005