20.500.12556/DKUM-20601 RAVNINSKOST GRAFOV PLANARITY OF GRAPHS 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 podgrafa, ki je subdivizija 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 podgraf, ki je subdivizija 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 graf G ne moremo razstaviti v k-1 ravninskih grafov. Na koncu diplomske naloge še predstavimo Heawood-ov problem dežel. Heawood je dokazal, da je vsak zemljevid 2-dežel lahko pobarvan z 12 barvami in obstaja zemljevid 2-dežel, ki potrebuje 12 barv. 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. ravninskost grafov subdivizija grafa prekrižno število debelina grafa delitveno število Heawood-ov problem dežel planar graphs subdivision of a graph crossing number thicknesses splitting number Heawood's empire problem true true false [K. Fotivec] Slovenski jezik Angleški jezik Diplomsko delo 2011-09-24 20:35:56 2011-10-10 15:07:12 2022-04-14 08:04:39 2023-12-27 03:19:28 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 18674184 URN:SI:UM:DK:ONPCROFS UNI_Fotivec_Kristjan_2011.pdf UNI_Fotivec_Kristjan_2011.pdf 1 D768AA7121971B852165871D65B779C4 254b9b83a1e814262b8d742f2c0439b09bf73f235b78b32d48e505e91e539f9e a860b6b5-7c05-11eb-bb7a-00155d0001ca 20.500.12556/dkum/af2d8e66-21c9-45a7-a0bb-2706a8a357df https://dk.um.si/Dokument.php?lang=slv&id=25623 Fakulteta za naravoslovje in matematiko 0 0 0