Hamiltonska razčlenitev grafa in otroški plesi

diplomsko delo

Nuša Butala (Author), Boštjan Kuzman (Mentor)

Abstract

Hamiltonska faktorizacija grafa je 2-faktorizacija grafa na hamiltonske cikle. V diplomskem delu se osredotočimo na iskanje hamiltonske razčlenitve ali faktorizacije grafov K_(2n+1), K_(n,n) in K_2n- 〖nK〗_2 ter iskanja 1-faktorizacije grafov K_2n in K_(n,n). Pred tem na začetku definiramo splošne definicije in grafovske lastnosti, ki jih potrebujemo za nadaljnje razumevanje dela. To so hamiltonske poti, prirejanja ter faktorji. V razdelku o prirejanjih dokažemo Tutteov izrek, v razdelku o faktorjih in faktorizaciji pa, kdaj je graf 1-faktorabilen oziroma 2-faktorabilen. Iskanje faktorizacije v tretjem poglavju prikažemo na primeru otroških plesov, kot jih je predstavil Édouard Lucas. Vse ponazorimo s preprostimi primeri. Za nekatere primere izdelamo programsko kodo, ki problem faktorizacije reši za konkreten n.

Keywords

faktor;1-faktorizacija;2-faktorizacija;hamiltonska faktorizacija;

Data

Language:	Slovenian
Year of publishing:	2017
Typology:	2.11 - Undergraduate Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[N. Butala]
UDC:	51(043.2)
COBISS:	11694409
Views:	834
Downloads:	166
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Hamiltonian factorization of a graph and children's dances
Secondary abstract:	Hamiltonian factorization of a graph is a 2-factorization of the graph into Hamiltonian cycles. In this thesis we focus on finding Hamiltonian factorization or decomposition of graphs K_(2n+1), K_(n,n), K_2n- 〖nK〗_2 and finding 1-factorization of graphs K_2n and K_(n,n). On start some general definitions and properties of a graph are needed to further understand the work. Among these are Hamiltonian paths, matchings and factors. In subsection on Matchings we prove Tutte’s theorem, in subsection of factors and factorization we define when the graph is 1-factorable or 2-factorable. In section three we present finding factorization on the example of children’s dances, as they were presented by Édouard Lucas. We illustrate these results with simple examples. For some examples we create a program code that solves the problem of factorization for concrete n.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. Ljubljana, Pedagoška fak., Dvopredmetni učitelj, Matematika in računalništvo
Pages:	26 str.
ID:	10864153