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

Abstract

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.

Keywords

matematika;grafi;ravninskost;subdivizija;prekrižno število;debelina grafa;delitveno število;diplomska dela;

Data

Language: Slovenian
Year of publishing:
Source: Maribor
Typology: 2.11 - Undergraduate Thesis
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
Publisher: [K. Fotivec]
UDC: 51(043.2)
COBISS: 18674184 Link will open in a new window
Views: 1814
Downloads: 187
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: PLANARITY OF GRAPHS
Secondary abstract: 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.
Secondary keywords: planar graphs;subdivision of a graph;crossing number;thicknesses;splitting number;Heawood's empire problem;
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: 41 f.
Keywords (UDC): mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID: 19531
Recommended works:
, 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