Lastnosti grafov Hanojskega stolpa

magistrsko delo

Eva Zmazek (Avtor), Sandi Klavžar (Mentor)

Povzetek

Hanojski grafi ▫$H_p^n$▫, ▫$n \geq 1$▫, ▫$p \geq 3$▫, so modeli predstavitve problema Hanojskega stolpa z ▫$n$▫ diski in ▫$p$▫ nosilci. Njihova rekurzivna konstrukcija vodi do izpeljave nekaterih lastnosti. Kromatično število ▫$\chi(H_p^n)$▫ Hanojskega grafa ▫$H_p^n$▫ je na primer enako številu nosilcev ▫$p$▫ prirejenega problema Hanojskega stolpa, kromatični indeks ▫$\chi'(H_p^n)$▫ tega Hanojskega grafa pa je enak njegovi maksimalni stopnji vozlišč ▫$\Delta(H_p^n)$▫. Vsi Hanojski grafi so Hamiltonovi, ▫$(p-1)$▫-povezani, nekateri med njimi so tudi ravninski. Barvanje povezav ▫$c: E(G) \to [k]$▫ je mavrica, če za poljubni različni povezavi ▫$e,f \in E(G)$▫ velja ▫$c(e) \not= c(f)$▫. Anti-Ramseyevo število na paru grafov ▫$G$▫ in ▫$H$▫ je najmanjše tako število ▫$n$▫, za katerega pri vsakem barvanju ▫$c$▫ povezav grafa ▫$G$▫ z natanko ▫$n$▫ barvami, obstaja ▫$H$▫-podgraf grafa ▫$G$▫, za katerega je zožitev ▫$c|H$▫ mavrica. V magistrski nalogi si ogledamo anti-Ramseyeva števila ▫$ar(H_p^n,H_q^m)$▫, ▫$p,q \geq 3$▫, ▫$n,m \geq 1$▫, na paru Hanojskih grafov, kjer je ▫$m=n=1$▫ in ▫$q=3$▫, in na paru Hanojskih grafov, kjer je ▫$p=q$▫. Za anti-Ramseyevo število ▫$ar(H_p^n,H_3^1)$▫, ▫$p \geq 3$▫, ▫$n \geq 1$▫, izpeljemo rekurzivno zvezo. Pokažemo tudi, da je anti-Ramseyevo število ar ▫$(H_4^2,H_3^2)$▫ omejeno navzdol s ▫$30$▫ ter navzgor s ▫$34$▫.

Ključne besede

magistrska dela;Hanojski graf;Hanojski stolp;anti-Ramseyevo število;mavrica;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[E. Zmazek]
UDK:	519.17(043.2)
COBISS:	24867592
Št. ogledov:	537
Št. prenosov:	84
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Properties of the graphs of the Tower of Hanoi
Sekundarni povzetek:	For integers ▫$n \geq 1$▫ and ▫$p \geq 3$▫ we define Hanoi graph ▫$H_p^n$▫ as a graph model of Tower of Hanoi with ▫$n$▫ discs and ▫$p$▫ pegs. Because of their recursive construction, there are some nice properties of Hanoi graphs. For example, the chromatic number ▫$\chi(H_p^n)$▫ of Hanoi graph ▫$H_p^n$▫ is equal to the number of pegs ▫$p$▫ and the chromatic index ▫$\chi'(H_p^n)$▫ of the same Hanoi graph is equal to its maximum degree of a vertex, ▫$\Delta(H_p^n)$▫. Each Hanoi graph ▫$H_p^n$▫ is Hamiltonian and ▫$(p-1)$▫-connected, and some of them are also planar. Edge coloring ▫$c: E(G) \to [k]$▫ of graph ▫$G$▫ is a rainbow if all of its edges are colored with different colors. Anti-Ramsey number for a pair of graphs ▫$G$▫ and ▫$H$▫ is the lowest number ▫$n$▫ such that for every edge coloring ▫$c$▫ of graph ▫$G$▫ with exactly ▫$n$▫ colors there exists such ▫$H$▫-subgraph of graph ▫$G$▫ that the coloring ▫$c$▫ on it is a rainbow. In the thesis, we present the exact value of anti-Ramsey numbers ▫$ar(H_p^n,H_q^m)$▫, ▫$p,q \geq 3$▫, ▫$n,m \geq 1$▫, for pairs of Hanoi graph where ▫$n=m=1$▫ ▫$q=3$▫ and also for pairs of Hanoi graphs where ▫$p=q$▫. For anti-Ramsey number ▫$ar(H_p^n,H_3^1)$▫, ▫$p \geq 3$▫, ▫$n \geq 1$▫ we give the recursive formula. We also show that the exact value of the anti-Ramsey number ar ▫$(H_4^2,H_3^2)$▫ is bounded with ▫$30$▫ and ▫$34$▫.
Sekundarne ključne besede:	master theses;Hanoi graph;tower of Hanoi;anti-Ramsey number;rainbow;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	VIII, 73 str.
ID:	11198525