Hamiltonska razčlenitev grafa in otroški plesi

diplomsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2017
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[N. Butala]
UDK:	51(043.2)
COBISS:	11694409
Št. ogledov:	834
Št. prenosov:	166
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Hamiltonian factorization of a graph and children's dances
Sekundarni povzetek:	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.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Komentar na gradivo:	Univ. Ljubljana, Pedagoška fak., Dvopredmetni učitelj, Matematika in računalništvo
Strani:	26 str.
ID:	10864153