diplomsko delo
Kristjan Fotivec (Avtor), Petra Žigert Pleteršek (Mentor)

Povzetek

V diplomskem delu predstavimo merjenja ravninskosti grafov. Graf G je ravninski, če ga lahko narišemo v ravnini tako, da noben par povezav nima skupnega vozlišča, razen v vozlišču, ki je njuno skupno krajišče. Obravnavamo načine za določanje ravninskosti s pomočjo metode iskanja pod grafa, ki je sub divizija od K5 ali K3,3, določanja prekrižnega števila, debeline grafov in delitvenega števila pri določenih grafov. Grafa K5 in K3,3 nista ravninska grafa, torej če G vsebuje pod graf, ki je sub divizija od K5 ali K3,3, potem G ni ravninski. Debelina grafa G, t(G), je minimalno število ravninskih grafov, iz katerih lahko sestavimo graf G. Torej t(G) = k pomeni, da je enak G = H1UH2U, ... ,Hk, kjer je Hi ravninski za vsaki i in grafa G ne moremo razstaviti v k - 1 ravninskih grafov. Na koncu diplomskega dela predstavimo Heawoodov problem dežel. Heawood je dokazal, da je vsak zemljevid dveh dežel lahko pobarvan z 12 barvami in obstaja zemljevid treh dežel, ki potrebuje 12 barv.

Ključne besede

matematika;grafi;ravninskost;subdivizija;prekrižno število;debelina grafa;delitveno število;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: [K. Fotivec]
UDK: 51(043.2)
COBISS: 18674184 Povezava se bo odprla v novem oknu
Št. ogledov: 1814
Št. prenosov: 187
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: PLANARITY OF GRAPHS
Sekundarni povzetek: In this diploma work we introduce planarity of graphs. Graph G is planar, if we can draw it in the plain so that no pair of edges intersect in the same vertex, except in theirs endvertices. We check the planarity of a graph with the examination of its subgraph. If the graph G has a subgraph, that is a subdivision of K5 or K3,3 then G is not planar. If a graph is not planar, we are interested in its crossing number, thicknesses and splitting number. The tickness of a graph G, denoted by t(G), is the minimum number of planar subgraphs in a decomposition of G into planar subgraphs. So t(G) = k means there is a decomposition of G = H1UH2U, ... ,Hk, where Hi is planar for each i and there is no decomposition of G into k - 1 planar subgraphs. At the end of the diploma we introduce Heawood's empire problem. Heawood prove, that every 2-pire map can be colored by twelve colors and there exist a 3-pire map that require twelve colors.
Sekundarne ključne besede: planar graphs;subdivision of a graph;crossing number;thicknesses;splitting number;Heawood's empire problem;
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: 41 f.
Ključne besede (UDK): mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID: 19531
Priporočena dela:
, diplomsko delo
, Seminar on algebraic combinatorics, Ben-Gurion University of the Negev, Beer Sheva, Israel, June 25, 2008
, Group Theory Seminar, 21.5.2008, Ohio State University, Columbus, Ohio, USA
, Seminar on algebraic combinatorics, Ben-Gurion University of the Negev, Beer Sheva, Israel, April 10, 2002
, Visiting Assistant Professor, 1.10.-31.12.2008, Ohio State University, Columbus, Ohio, USA