Hamiltonska povezanost Cayleyjevih grafov komutativnih grupPetek, Ana (Avtor) Šparl, Primož (Mentor) Cayleyjev grafV 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.20182018-12-04 02:55:12Magistrsko delo/naloga105515COBISS_ID: 12224073sl