Hamiltonska dopolnitev grafa

diplomsko delo

Nataša Brodnjak (Author), Matjaž Kovše (Mentor)

Abstract

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.

Keywords

matematika;grafi;hamiltonski graf;dopolnitev grafa;poti;pokrivanje;frekvence;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[N. Brodnjak]
UDC:	51(043.2)
COBISS:	18504456
Views:	1612
Downloads:	94
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	HAMILTONIAN COMPLETION OF A GRAPH
Secondary abstract:	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.
Secondary keywords:	Hamiltonian graph;Hamiltonian completion of a graph;path cover for a graph;frequency assignment;
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:	39 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19359