RAVNINSKOST GRAFOVFotivec, Kristjan (Avtor) Žigert, Petra (Mentor) ravninskost grafovsubdivizija grafaprekrižno številodebelina grafadelitveno številoHeawood-ov problem deželV 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. [K. Fotivec]20112011-09-24 20:35:56Diplomsko delo20601UDK: 51(043.2)COBISS_ID: 18674184NUK URN: URN:SI:UM:DK:ONPCROFSsl