Hamiltonska razčlenitev grafa in otroški plesi : diplomsko delo

Butala, Nuša (author), Kuzman, Boštjan (mentor)

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.

• Language: Slovenian
• Keywords: faktor, 1-faktorizacija, 2-faktorizacija, hamiltonska faktorizacija
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: PEF - Faculty of Education
• Publisher: [N. Butala]
• Year: 2017
• Number of pages: 26 str.
• PID: 20.500.12556/RUL-95147
• UDC: 51(043.2)
• COBISS.SI-ID: 11694409
• Publication date in RUL: 19.09.2017

BUTALA, Nuša, 2017, Hamiltonska razčlenitev grafa in otroški plesi : diplomsko delo [online]. Bachelor’s thesis. N. Butala. [Accessed 11 April 2025]. Retrieved from: http://pefprints.pef.uni-lj.si/id/eprint/4652

Secondary language

• Language: English
• Title: Hamiltonian factorization of a graph and children's dances

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.

• Keywords: mathematics, matematika