20.500.12556/DKUM-18995 HAMILTONSKA DOPOLNITEV GRAFA HAMILTONIAN COMPLETION OF A GRAPH Diplomsko delo obravnava hamiltonsko dopolnitev grafa. Število hamiltonske dopolnitve grafa G je najmanjše število povezav, ki jih moramo dodati grafu, da ta postane hamiltonski graf. V prvem poglavju predstavimo osnovne definicije iz teorije grafov in algoritmov, ki jih potrebujemo v nadaljevanju. Nato definiramo problem hamiltonske dopolnitve grafa ter soroden problem pokrivanja vozlišč s potmi. V tretjem poglavju predstavimo algoritma za hamiltonsko dopolnitev dreves. V četrtem poglavju opišemo reševanje hamiltonske dopolnitve grafa za poljuben graf. Na koncu diplomskega dela opišemo sorodne probleme. The thesis is about the Hamiltonian completion of a graph G. We define the Hamiltonian completion number of a graph G, to be the minimum number of edges to be added to G in order to make it Hamiltonian. In the first chapter the basic defnitions from graph theory and algorithms, necessary for our purpose, are presented. Then the Hamiltonian completion problem and the similar problem of a path cover are defned. The third chapter is about the algorithms for the Hamiltonian completion for trees. In the fourth chapter the Hamiltonian completion problem for an arbitrary graph is considered. The thesis ends with a description of the problems, similar to the Hamiltonian completion problem. hamiltonski graf hamiltonska dopolnitev grafa pokrivanje s potmi dodeljevanje frekvenc Hamiltonian graph Hamiltonian completion of a graph path cover for a graph frequency assignment true true false [N. Brodnjak] Slovenski jezik Angleški jezik Diplomsko delo 2011-06-14 18:48:35 2011-07-07 12:57:28 2022-04-13 14:59:43 2023-12-24 03:31:52 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 18504456 URN:SI:UM:DK:ZLBJ8EKJ UNI_Brodnjak_Natasa_2011.pdf UNI_Brodnjak_Natasa_2011.pdf 1 D1098581F002172768B9245F98B2CA9B 567b5045a4fdfee810bebaed505098be890acb4486dd7b44228713ac98ef2f22 444afc57-7c05-11eb-bb7a-00155d0001ca 20.500.12556/dkum/b1dee999-0ccf-41fc-907a-0e09b66a029a https://dk.um.si/Dokument.php?lang=slv&id=22775 Fakulteta za naravoslovje in matematiko 0 0 0