izpis_h1_title_alt

Hamiltonian cycles in neighbor-swap graphs : master's thesis
ID Smerdu, Ana (Avtor), ID Verhoeff, Tom (Mentor) Več o mentorju... Povezava se odpre v novem oknu, ID Žitnik, Arjana (Komentor)

.pdfPDF - Predstavitvena datoteka, prenos (6,16 MB)
MD5: 986DE7C124F2728CF2F9BA9370BAC158

Izvleček
In 1965 Derrick Henry Lehmer conjectured that every neighbor-swap graph admits an imperfect Hamiltonian path. This path, also known as Lehmer path, is a walk visiting all the vertices of a graph where some of them might be visited twice in a row. For most of the neighbor-swap graphs the conjecture is already proved, it remains open only for two families of graphs. We will present known results with their proofs in the thesis. It turns out most of these graphs even contain a Lehmer cycle and we will show how to construct them. For the missing part of the proof we will present a possible approach, that might finally confirm D. H. Lehmer's conjecture. First we find a Hamiltonian path in a related binary neighbor-swap graph and then step by step add the missing symbols, connecting the paths together into a Lehmer path.

Jezik:Angleški jezik
Ključne besede:neighbor-swap graphs, multisets, permutations, transpositions, Hamiltonian paths, Lehmer paths, posets
Vrsta gradiva:Magistrsko delo/naloga
Tipologija:2.09 - Magistrsko delo
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2019
PID:20.500.12556/RUL-108786 Povezava se odpre v novem oknu
UDK:519.17
COBISS.SI-ID:18676313 Povezava se odpre v novem oknu
Datum objave v RUL:25.07.2019
Število ogledov:1324
Število prenosov:253
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Hamiltonovi cikli v grafih transpozicij sosedov
Izvleček:
Lehmerjeva pot je nepopolna Hamiltonova pot in je definirana kot sprehod, kjer obiščemo vsa vozlišča v grafu, nekatera pa lahko obiščemo dvakrat zapored. Leta 1965 je Derrick Henry Lehmer postavil domnevo, da vsak graf transpozicij sosedov vsebuje Lehmerjevo pot. Domneva je v veliki meri že dokazana in te izreke z dokazi bomo v magistrski nalogi tudi predstavili. Izkaže se, da je v mnogih primerih možna celo konstrukcija Lehmerjevega cikla, kar bomo tudi pokazali. Za mankajoči del dokaza bomo podali možen pristop, ki bi domnevo D. H. Lehmerja dokončno potrdil. Najprej poiščemo Hamiltonovo pot v sorodnem dvojiškem grafu transpozicij sosedov, nato pa s konstrukcijo Stachowiaka postopoma dodajamo manjkajoče simbole in združujemo dobljene Lehmerjeve poti.

Ključne besede:graf transpozicij sosedov, večkratne množice, permutacije, transpozicije, Hamiltonove poti, Lehmerjeve poti, delno urejene množice

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj