Razčlenitve grafovStojko, Jera (Avtor) Kuzman, Boštjan (Mentor) razčlenitev grafaMagistrsko delo je s področja teorije grafov, natančneje, govori o razčlenitvi grafov. Različne oblike razčlenitve grafov se v praksi pogosto pojavljajo v problemih razporejanja objektov v skupine s posebnimi lastnostmi, zato jih srečujemo na različnih področjih od računalniških algoritmov do socialnih omrežij in matematičnih ugank. Razčlenitev ali dekompozicija grafa je zapis grafa z unijo podgrafov, tako da vsaka povezava grafa pripada natanko enemu podgrafu. V delu obravnavamo različne vrste razčlenitev. Če so podgrafi med seboj izomorfni, govorimo o izomorfni razčlenitvi grafa. Posebna oblika razčlenitve je faktorizacija. V tem primeru graf razčlenimo na vpete podgrafe. Poseben primer faktorizacije je k-faktorizacija, to je razčlenitev grafa na k-regularne vpete podgrafe. Pri vrednosti k=1 dobimo razčlenitev na 1-faktorje, ki jih z drugo besedo imenujemo popolna prirejanja. Gre za faktorizacijo na največje možno število izomorfnih faktorjev. V primeru 2-faktorizacije pa gre za razčlenitev na unije ciklov. Posebej lahko obravnavamo tudi drugačne razčlenitve. Za boljšo predstavo in razumevanje so predstavljeni zgledi razčlenitev in faktorizacij grafov. V delu se posebej posvetimo izomorfni faktorizaciji polnih grafov. Podan je dokaz izreka o deljivosti, ki so ga dokazali Harary, Robinson in Wormald [8]. Izrek o deljivosti nam pove, da polni graf reda n lahko razčlenimo na t izomorfnih faktorjev natanko tedaj, ko t deli število povezav polnega grafa. Dokaz izreka je konstruktiven in vsebuje opis konstrukcije ustreznih faktorjev za različne vrednosti parametrov n in t. Kot zgled uporabe tega izreka v poglavju o trideljivosti določimo vseh 9 tridelitev polnega grafa K6 in opišemo, kako bi poiskali vseh 41 tridelitev polnega grafa K7. V nadaljevanju predstavimo nekatere izreke o izomorfni razčlenitvi polnih grafov na največ možnih faktorjev (1-faktorizacija), na 2 izomorfna faktorja (sebi-komplementarni grafi), na poti ter na cikle (2-faktorizacija). Delitev na cikle je ločena na hamiltonske cikle, cikle poljubnih dolžin in najkrajše 3-cikle. Problem razčlenitve polnih grafov na 3-cikle je povezan s Steinerjevimi sistemi trojic. Torej, koliko trojic lahko sestavimo z danimi elementi, da bo vsak par elementov ležal v natanko eni od trojic. O razčlenitvi polnih grafov na cikle poljubnih dolžin nam govori domneva B. Alspacha, ki so jo nedavno dokazali D. Bryant in sodelavci [5]. V zvezi z razčlenitvijo grafov ostaja mnogo nerešenih domnev. Ena izmed njih je omenjena v nalogi. Govori o razčlenitvi polnih grafov na poljubne vnaprej predpisane izomorfne podgrafe, na primer drevesa. Ringel in Kotzig sta ugotovila, da je razčlenitev polnega grafa reda 2n+1 zagotovo možna na podgrafe velikosti n, če ima podgraf posebno lastnost, ki jo danes imenujemo, da je ``ljubek''. Izoblikovala se je domneva, da so vsa drevesa ljubka. V zaključku je predstavljenih še nekaj z razčlenitvami povezanih kombinatoričnih ugank, ki bi jih lahko uporabili tudi pri pouku matematike.20192019-09-25 03:19:47Magistrsko delo/naloga111114COBISS_ID: 12601673sl