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

Butala, Nuša (avtor), 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.

• Jezik: Slovenski jezik
• Ključne besede: faktor, 1-faktorizacija, 2-faktorizacija, hamiltonska faktorizacija
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: PEF - Pedagoška fakulteta
• Založnik: [N. Butala]
• Leto izida: 2017
• Št. strani: 26 str.
• PID: 20.500.12556/RUL-95147
• UDK: 51(043.2)
• COBISS.SI-ID: 11694409
• Datum objave v RUL: 19.09.2017

BUTALA, Nuša, 2017, Hamiltonska razčlenitev grafa in otroški plesi : diplomsko delo [na spletu]. Diplomsko delo. N. Butala. [Dostopano 7 april 2025]. Pridobljeno s: http://pefprints.pef.uni-lj.si/id/eprint/4652

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Hamiltonian factorization of a graph and children's dances

Izvleček

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.

• Ključne besede: mathematics, matematika