Hamiltonska dopolnitev grafa

diplomsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[N. Brodnjak]
UDK:	51(043.2)
COBISS:	18504456
Št. ogledov:	1612
Št. prenosov:	94
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	HAMILTONIAN COMPLETION OF A GRAPH
Sekundarni povzetek:	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.
Sekundarne ključne besede:	Hamiltonian graph;Hamiltonian completion of a graph;path cover for a graph;frequency assignment;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	39 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19359