| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva Pomoč

Naslov:Lastnosti grafov Hanojskega stolpa
Avtorji:ID Zmazek, Eva (Avtor)
ID Klavžar, Sandi (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf MAG_Zmazek_Eva_2019.pdf (554,90 KB)
MD5: F41C06D194475BCD4D08ED876C4B1D47
PID: 20.500.12556/dkum/cc42130b-e693-415f-962c-388008f83675
 
Jezik:Slovenski jezik
Vrsta gradiva:Magistrsko delo/naloga
Tipologija:2.09 - Magistrsko delo
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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$.
Ključne besede:Hanojski graf, Hanojski stolp, anti-Ramseyevo število, mavrica
Kraj izida:Maribor
Založnik:[E. Zmazek]
Leto izida:2019
PID:20.500.12556/DKUM-74115 Novo okno
UDK:519.17(043.2)
COBISS.SI-ID:24867592 Novo okno
NUK URN:URN:SI:UM:DK:WB8OWLPT
Datum objave v DKUM:05.11.2019
Število ogledov:1048
Število prenosov:121
Metapodatki:XML DC-XML DC-RDF
Področja:FNM
:
ZMAZEK, Eva, 2019, Lastnosti grafov Hanojskega stolpa [na spletu]. Magistrsko delo. Maribor : E. Zmazek. [Dostopano 16 marec 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=74115
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:07.08.2019

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Properties of the graphs of the Tower of Hanoi
Opis: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.
Ključne besede:Hanoi graph, Tower of Hanoi, anti-Ramsey number, rainbow


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici