Slučajni grafi
diplomsko delo
Abstract
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.
Keywords
matematika;slučajni grafi;matematično upanje;Markova neenakost;verjetnostni model;pragovna funkcija;drugi moment;metoda;diplomska dela;
Data
| Language: | Slovenian |
|---|---|
| Year of publishing: | 2012 |
| Source: | Maribor |
| Typology: | 2.11 - Undergraduate Thesis |
| Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
| Publisher: | [M. Pasterk] |
| UDC: | 51(043.2) |
| COBISS: |
19136264
|
| Views: | 1562 |
| Downloads: | 145 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary title: | RANDOM GRAPHS |
| Secondary abstract: | 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. |
| Secondary keywords: | random graph;expectation;Markov’s inequality;probability model;threshold function;second moment method; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Undergraduate thesis |
| Thesis comment: | Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo |
| Pages: | 27 f. |
| Keywords (UDC): | mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika; |
| ID: | 19935 |
Recommended works:
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