izpis_h1_title_alt

Hipohamiltonovi grafi
Šubic, Alja (Avtor), Šparl, Primož (Mentor) Več o mentorju... Povezava se odpre v novem oknu

URLURL - Predstavitvena datoteka, za dostop obiščite http://pefprints.pef.uni-lj.si/5683/ Povezava se odpre v novem oknu

Izvleček
V teoriji grafov, področju na katero sodi to magistrsko delo, so zelo zanimiv predmet raziskovanja Hamiltonovi grafi. To so grafi, ki premorejo Hamiltonov cikel oziroma cikel, ki vsebuje vsa vozlišča danega grafa, vsako natanko enkrat. V magistrskem delu se ukvarjamo s posebno vrsto nehamiltonovih grafov, ki pa so skoraj Hamiltonovi. Gre za tako imenovane hipohamiltonove grafe, ki sicer ne premorejo Hamiltonovega cikla, ob odstranitvi poljubnega vozlišča iz prvotnega grafa pa dobljeni inducirani podgraf postane Hamiltonov. Glavni namen magistrskega dela je podrobna predstavitev koncepta hipohamiltonskosti, predstavitev več vrst različnih primerov takšnih grafov, predvsem pa se posvetimo vprašanju, za katera naravna števila n obstaja vsaj en hipohamiltonov graf reda n. Ob koncu magistrskega dela nekaj pozornosti namenimo še kubičnim hipohamiltonovim grafom. Le-ti so za študij še posebej zanimivi, saj gre za grafe, katerih stopnje vozlišč so, ko govorimo o hipohamiltonovih grafih, najmanjše možne. Magistrskemu delu je dodana priloga, kjer sta podana programa za preverjanje hamiltonskosti in hipohamiltonskosti grafov nižjih redov, napisana v programskem jeziku Python. Z njima podkrepimo nekatere rezultate magistrskega dela, saj lahko na ta način preverimo, ali so grafi, ki so podani kot konkretni primeri majhnih hipohamiltonovih grafov, zares hipohamiltonovi.

Jezik:Slovenski jezik
Ključne besede:Hamiltonov cikel
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Tipologija:2.09 - Magistrsko delo
Organizacija:PEF - Pedagoška fakulteta
Leto izida:2019
COBISS.SI-ID:12378185  Povezava se odpre v novem oknu
Število ogledov:163
Število prenosov:70
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Hypohamiltonian graphs
Izvleček:
Hamiltonian graphs are a very interesting research subject in the field of graph theory, which is the subject of this master’s thesis. These are the graphs that contain a Hamiltonian cycle, that is a cycle which contains all the vertices of the given graph, each exactly once. In this master’s thesis we deal with a special type of non-hamiltonian graphs, which are almost Hamiltonian. In particular, we study the so-called hypohamiltonian graphs, which don’t contain a Hamiltonian cycle but after removing any vertex from the original graph we get an induced subgraph which is Hamiltonian. The main purpose of the master’s thesis is a detailed presentation of the concept of hypohamiltonicity and the presentation of many kinds of different examples of such graphs. A special emphasis is put on the problem of determining all natural numbers n for which there is at least one hypohamiltonian graph of order n. At the end of this master's thesis we devote some attention to cubic hypohamiltonian graphs. These are particularly interesting for this study as the degrees of vertices of such graphs are the least possible when considering hypohamiltonian graphs.

Ključne besede:Hamiltonian cycle

Podobna dela

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

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

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

Nazaj