magistrsko delo
Ana Petek (Avtor), Primož Šparl (Mentor)

Povzetek

V magistrskemu delu se ukvarjamo z znano družino precej simetričnih grafov. To so tako imenovani Cayleyjevi grafi. V zvezi z njimi je zanimivo vprašanje o obstoju hamiltonskih poti oziroma hamiltonskih ciklov v takšnih grafih. Cayleyjevi grafi so grafi, katerih vozlišča so elementi dane grupe, povezave pa so dane s pomočjo tako imenovane povezavne množice. Hamiltonska pot je pot, ki obišče vsa vozlišča danega grafa, vsako natanko enkrat. Podobno je hamiltonski cikel cikel, ki vsebuje vsa vozlišča danega grafa. Glavna tema magistrskega dela je vprašanje, ali med poljubnima vozliščema v Cayleyjevem grafu komutativne oziroma abelske grupe obstaja hamiltonska pot ali ne. Govorimo o hamiltonski povezanosti grafa. Pri tem natančno preučimo in analiziramo rezultate Chena in Quimpa iz članka [6]. Na začetku si podrobneje pogledamo, kako je z obstojem hamiltonskih poti v kartezi čnemu produktu dveh poti ali cikla in poti. S pomočjo pridobljenih rezultatov potem analiziramo obstoj hamiltonskih poti med poljubnimi vozlišči v Cayleyjevih grafih komutativnih grup, saj v njih najdemo takšne vpete podgrafe. Rezultate nato posplošimo še na Cayleyjeve grafe komutativnih grup, ki so dvodelni. Slednji so zanimivi predvsem zato, ker z eno izjemo niso hamiltonsko povezani. Namesto tega so lahko hamiltonsko vezljivi, kjer zahtevamo hamiltonske poti le med poljubnimi vozlišči iz različnih delov dvodelnega razbitja. Na koncu si pogledamo še katere znane družine grafov so v resnici Cayleyjevi grafi komutativnih grup in zato zanje lahko uporabimo omenjeni izrek. Dodatno omenimo še Johnsonove grafe in si pogledamo, kako je z njihovo hamiltonsko povezanostjo. Na kratko komentiramo tudi pomembnost in uporabnost izreka [6], ki ga v svojih člankih kot ključni vir navajajo številni avtorji.

Ključne besede

Cayleyjev graf;hamiltonski cikel;hamiltonska pot;hamiltonska povezanost;hamiltonska vezljivost;komutativna (abelska) grupa;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL PEF - Pedagoška fakulteta
Založnik: [A. Petek]
UDK: 51(043.2)
COBISS: 12224073 Povezava se bo odprla v novem oknu
Št. ogledov: 543
Št. prenosov: 106
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Hamiltonian connectedness of Cayley graphs of abeliangroups
Sekundarni povzetek: In the master thesis we are dealing with a very well known family of graphs with a lot of symmetry, namely with the so-called Cayley graphs. Regarding them there is an interesting question about the existence of hamiltonian paths and hamiltonian cycles in such graphs. Cayley graphs are graphs whose vertices are elements of a given group, while the edges are given via a suitable generating set. A hamiltonian path of a graph is path that visits all the vertices of a given graph, each exactly once. Similarly, a hamiltonian cycle is a cycle that consists of all the vertices of a given graph. The main topic of this thesis is the question about the existence of hamiltonian paths between any two vertices in Cayley graphs of abelian groups. Graphs with this property are said to be hamiltonian connected. In the process, we thoroughly study the results of Chen and Quimpo from the article [6]. At the beginning we study the existence of hamiltonian paths in cartesian products of two paths or of a cycle and a path. With the help of the obtained results we then analyze the existence of hamiltonian paths between any two vertices in Cayley graphs of abelian groups, since we can �nd such spanning subgraphs in these graphs. The results are then generalized to Cayley graphs of abelian groups which are bipartite. The latter are particularly interesting because they are not generally hamiltonian connected. Instead of that they are hamiltonian laceable, where we only demand hamiltonian paths between two vertices from di�erent parts of the bipartition. Finally, we present same well-known graph families which are in fact Cayley graphs of abelian groups, and therefore we can use the above theorem for their members. Additionally, we mention Johnson's graphs and their hamiltonian connectedness. We also brie y comment on the importance and usefulness of the results from [6], which are mentioned by many authors in their articles as a key step in their proofs.
Sekundarne ključne besede: mathematics;matematika;
Vrsta datoteke: application/pdf
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Ljubljani, Pedagoška fak., Poučevanje, Predmetno poučevanje
Strani: 74 str.
ID: 10990584