| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document Help

Title:Lastnosti grafov Hanojskega stolpa
Authors:ID Zmazek, Eva (Author)
ID Klavžar, Sandi (Mentor) More about this mentor... New window
Files:.pdf MAG_Zmazek_Eva_2019.pdf (554,90 KB)
MD5: F41C06D194475BCD4D08ED876C4B1D47
PID: 20.500.12556/dkum/cc42130b-e693-415f-962c-388008f83675
 
Language:Slovenian
Work type:Master's thesis/paper
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Hanojski grafi Hnp, n1, p3, so modeli predstavitve problema Hanojskega stolpa z n diski in p nosilci. Njihova rekurzivna konstrukcija vodi do izpeljave nekaterih lastnosti. Kromatično število χ(Hnp) Hanojskega grafa Hnp je na primer enako številu nosilcev p prirejenega problema Hanojskega stolpa, kromatični indeks χ(Hnp) tega Hanojskega grafa pa je enak njegovi maksimalni stopnji vozlišč Δ(Hnp). Vsi Hanojski grafi so Hamiltonovi, (p1)-povezani, nekateri med njimi so tudi ravninski. \end{sloppypar} \begin{sloppypar} 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$.
Keywords:Hanojski graf, Hanojski stolp, anti-Ramseyevo število, mavrica
Place of publishing:Maribor
Publisher:[E. Zmazek]
Year of publishing:2019
PID:20.500.12556/DKUM-74115 New window
UDC:519.17(043.2)
COBISS.SI-ID:24867592 New window
NUK URN:URN:SI:UM:DK:WB8OWLPT
Publication date in DKUM:05.11.2019
Views:1048
Downloads:121
Metadata:XML DC-XML DC-RDF
Categories:FNM
:
ZMAZEK, Eva, 2019, Lastnosti grafov Hanojskega stolpa [online]. Master’s thesis. Maribor : E. Zmazek. [Accessed 16 March 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=74115
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:07.08.2019

Secondary language

Language:English
Title:Properties of the graphs of the Tower of Hanoi
Abstract:For integers n1 and p3 we define Hanoi graph Hnp 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 χ(Hnp) of Hanoi graph Hnp is equal to the number of pegs p and the chromatic index χ(Hnp) of the same Hanoi graph is equal to its maximum degree of a vertex, Δ(Hnp). Each Hanoi graph Hnp is Hamiltonian and (p1)-connected, and some of them are also planar. Edge coloring c:E(G)[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(Hnp,Hmq), p,q3, n,m1, 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(Hnp,H13), p3, n1 we give the recursive formula. We also show that the exact value of the anti-Ramsey number \ar(H24,H23) is bounded with 30 and 34.
Keywords:Hanoi graph, Tower of Hanoi, anti-Ramsey number, rainbow


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica