1. KARTEZIČNI PRODUKT GRAFOVIris Merkač, 2009, diplomsko delo Opis: Diplomsko delo je sestavljeno iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in podamo definicije ter osnovne lastnosti kartezičnega produkta dveh ali večih grafov.
V naslednjem poglavju podamo definiciji hiperkocke in delne kocke, ter spoznamo da so hiperkocke najpreprostejši razred kartezičnega produkta. Nato se posvetimo Djoković-Winklerjevi relaciji Θ, za katero ugotovimo, da je definirana na množici povezav grafa in da je bistvenega pomena za kartezični produkt. Poglavje zaključimo s preprostim algoritmom prepoznavanja hiperkock.
V zadnjem poglavju definiramo Hammingove grafe in delne Hammingove grafe. Opazimo tudi, da so hiperkocke edini dvodelni Hammingovi grafi. V nadaljevanju raziščemo kanonično vložitev grafov v kartezični produkt dveh ali večih kvocientnih grafov, katere dobimo iz ekvivalenčnih razredov tranzitivne ovojnice relacije Θ. Nato dokažemo Graham-Winklerjev izrek, ki pove, da je kanonična vložitev izometrija. Ker je izračunavanje tranzitivne ovojnice relacije Θ bistveno pri izračunavanju kanonične vložitve, na koncu podamo algoritem, ki izračuna tranzitivno ovojnico relacije Θ.
Ključne besede: kartezični produkt, hiperkocke, delne kocke, Hammingovi grafi, relacija Θ, kvocientni graf, kanonična vložitev
Objavljeno: 27.01.2021; Ogledov: 199; Prenosov: 12
 Celotno besedilo (411,17 KB) |
2. Nekatere s pakiranji povezane lastnosti grafovDragana Božović, 2020, doktorska disertacija Opis: V disertaciji se ukvarjamo z različnimi problemi, povezanimi s pakiranji. Disertacija je sestavljena iz štirih delov.
Prvi del je namenjen grafom, ki imajo enolično pakirno množico največje moči. Najprej predstavimo nekatere lastnosti teh grafov. Nato podamo še dve karakterizaciji dreves z enolično pakirno množico.
V drugem delu vpeljemo pojem dimenzije incidenčnosti, ki je neposredno povezana z 2-pakirnim številom grafa, in določimo formulo za njen izračun. Dokažemo, da je problem iskanja incidenčne dimenzije grafa v splošnem NP-poln.
Tretji del namenimo pakirnemu kromatičnemu številu leksikografskega produkta grafov. Določimo njegovo spodnjo in zgornjo mejo ter izboljšano zgornjo mejo za primer, ko je prvi faktor v produktu izomorfen poti.
V zadnjem delu se posvetimo učinkoviti odprti dominaciji produktov digrafov. Okarakteriziramo učinkovito odprto dominirane direktne in leksikografske produkte digrafov. Pri kartezičnem produktu okarakteriziramo tiste, kjer je prvi faktor usmerjena pot, usmerjen cikel ali zvezda z enim izvorom. Predstavimo tudi karakterizacijo učinkovito odprto dominiranega krepkega produkta, katerega temeljni graf obeh faktorjev je monocikličen graf.
Ključne besede: pakirna množica, enolično največje pakiranje, dimenzija incidenčnosti, generator incidenčnosti, pakirno kromatično število, leksikografski produkt grafov, učinkovita odprta dominacija, usmerjeni grafi, produkti usmerjenih grafov
Objavljeno: 27.11.2020; Ogledov: 297; Prenosov: 80
Celotno besedilo (753,30 KB) |
3. Število kromatične stabilnosti povezavTjaša Kos, 2020, magistrsko delo Opis: V magistrskem delu predstavimo število kromatične stabilnosti povezav grafa $G$. Najprej definiramo osnovne pojme teorije grafov in dokažemo nekaj lastnosti števila kromatične stabilnosti povezav. Opišemo grafe Mycielskega, njihovo konstrukcijo ter dokažemo, da je kromatično število grafa Mycielskega $M(G)$ za ena večje od kromatičnega števila grafa $G$. Nato se osredotočimo na število kromatične stabilnosti povezav posebnih družin grafov. Raziskujemo disjunktno unijo grafov, kartezični produkt, spoj grafov ter posebne družin grafov, ki jih dobimo s spojem nekaterih družin grafov. V nadaljevanju opišemo meje števila kromatične stabilnosti povezav. Dokažemo več spodnjih in zgornjih mej za $es_{\chi}(G)$. Osredotočimo se tudi na rezultate tipa Nordhaus-Gaddum in dokažemo zgornjo mejo za vsoto števila kromatične stabilnosti povezav grafa $G$ in njegovega komplementa $\overline{G}$. Nazadnje raziskujemo grafe z $es_{\chi}(G)=1$. Dokažemo, da je $es_{\chi}(G)=1$ natanko tedaj, ko je vezano kromatično število enako $1$. Še več, predstavimo več potrebnih pogojev za graf $G$ z $es_{\chi}(G)=1$.
Ključne besede: število kromatične stabilnosti povezav, kromatično število, dvodelni grafi, kartezični produkt grafov, grafi Mycielskega, neenakost tipa Nordhaus-Gaddum, vezano kromatično število
Objavljeno: 29.10.2020; Ogledov: 205; Prenosov: 23
Celotno besedilo (2,21 MB) |
4. Matematične uganke v teoriji grafovMaja Javornik, 2019, magistrsko delo Opis: V magistrskem delu je predstavljenih več učencem zanimivih matemati\v cnih ugank. Najprej obravnavamo različne matematične uganke skozi zgodovino vse od magi\v cnih kvadratov do ugank novej\v sega \v casa kot je rubikova kocka. Nato se osredotočimo na teorijo grafov in predstavimo ikozaedersko igro, problem Köningsber\v ski mostov, problem prečkanja reke brez mostov in problem \v stirih konjev. Kot uvod v obravnavo kitajskih prstanov predstavimo legendo o stolpu iz Brahme in vpeljemo Hanojske stolpe. Doka\v zemo optimalno re\v sitev Hanojskega stolpa z $n \in{\mathbb{N}}_0$ diski. Med drugimi predstavimo variacijo Hanojskega stolpa, ki se imenuje zamenjevalni Hanojski stolp in predstavimo zgodovino kitajskih prstanov. Nazadnje problem kitajskih prstanov podrobneje raziščemo in doka\v zemo formulo za najhitrejšo rešitev problema.
Ključne besede: Kitajski prstani, Hanojski stolpi, Hamiltonovi grafi, Eulerjevi grafi, ravninski grafi
Objavljeno: 23.01.2020; Ogledov: 489; Prenosov: 58
Celotno besedilo (3,34 MB) |
5. Igra policajev in roparjev na grafihTina Bastašić, 2019, magistrsko delo Opis: V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G.
Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi.
Ključne besede: igra policajev in roparjev, varnostno število grafa, policaj-zmaga grafi, odstranljivi grafi, mostovni grafi
Objavljeno: 05.11.2019; Ogledov: 531; Prenosov: 66
Celotno besedilo (318,60 KB) |
6. Nekatere lastnosti posplošenih grafov SierpińskegaTeja Bezgovšek, 2019, magistrsko delo Opis: V magistrskem delu so obravnavane in s slikovnimi zgledi predstavljene nekatere lastnosti posplošenih grafov Sierpińskega, zgrajenih na poljubnem baznem grafu G. V prvem poglavju so povzete osnovne definicije iz teorije grafov, ki so pomembne pri razumevanju magistrskega dela. Nato so predstavljeni grafi Sierpińskega in definirani posplošeni grafi Sierpińskega. Tretje poglavje obravnava popolno kromatično število obravnavanih grafov, med drugim tudi za konkretne primere baznih grafov, in sicer graf hiše, kolo, cikel in hiperkocko. V četrtem poglavju so z zgledi podane formule za izračun števila listov, število vozliščnega pokritja in neodvisno število v posplošenih grafih Sierpińskega. V poglavju je tudi dokazano, da sta kromatično in klično število teh grafov enaka kot v bazi. V nadaljevanju je podana zgornja meja dominacijskega števila obravnavanih grafov in tudi točno dominacijsko število teh grafov z dotičnimi lastnostmi. V zadnjem poglavju je dokazana spodnja meja krepke metrične dimenzije posplošenih grafov Sierpińskega in podana je formula za izračun te lastnosti v obravnavanih grafih, v katerih je vsako notranje vozlišče presečno vozlišče.
Ključne besede: posplošeni grafi Sierpińskega, popolno kromatično število, število vozliščnega pokritja, dominacijsko število, krepka metrična dimenzija.
Objavljeno: 04.03.2019; Ogledov: 533; Prenosov: 63
Celotno besedilo (627,83 KB) |
7. Dominacija v grafih in ravninski grafi pri pouku v osnovni in srednji šoliIlija Ilić, 2018, magistrsko delo Opis: V magistrskem delu so predstavljene izbrane vsebine iz teorije grafov s poudarkom na dominacijah v grafih in na ravninskih grafih. V teoretičnem delu so navedene vse potrebne definicije, izreki, trditve in dokazi obravnavanih vsebin, poleg tega pa je predstavljena tudi didaktična teorija o izvajanju pouka.
V praktičnem delu so nato predstavljeni primeri izbranih obravnav omenjenih vsebin pri pouku v osnovnih in srednjih šolah. Vsebine so zastavljene kot celovita osnova za nadaljnje načrtovanje učnih priprav in zajemajo teoretične razlage, naloge z grafičnim gradivom in rešitvami ter didaktične nasvete za predstavitev vsebin.
Ključne besede: dominacija v grafih, ravninski grafi, teorija grafov pri pouku v osnovni in srednji šoli
Objavljeno: 27.09.2018; Ogledov: 529; Prenosov: 68
Celotno besedilo (2,37 MB) |
8. Naravoslovni postopki pri kemijskih vsebinah v drugem triletju osnovne šoleJulija Murko, 2018, magistrsko delo Opis: Naravoslovni postopki so temelj začetnega naravoslovja. Med naravoslovne postopke uvrščamo tudi delo s podatki, ki zajema interpretiranje, risanje in branje grafov. Na razumevanje in branje grafov pogosto naletimo v vsakdanjem življenju, saj so grafi prisotni na veliko področjih življenja, od čisto osebnih do strokovnih oz. poklicnih. Branje in risanje prikazov oz. grafov pa ima tudi pri pouku naravoslovja pomembno vlogo. Mnogi domači in tuji strokovnjaki poudarjajo pomembnost aktivne vpeljave grafov v pouk naravoslovja. Takšen način dela pri pouku predlagajo tudi slovenski učni načrti. V magistrskem delu so prikazani rezultati raziskave med 134 učenci 5. in 6. razreda osnovne šole, kjer nas je zanimalo, kako učenci rišejo, berejo in razumejo grafe pri pouku naravoslovja v drugem triletju osnovne šole. Ugotovili smo, da je znanje učencev, vključenih v raziskavo, v povprečju slabo (73 % učencev na testu ni doseglo polovice možnih točk). Sicer pa učenci bolje berejo in napovedujejo grafe, slabše pa razumejo pojme: odvisna in neodvisna spremenljivka ter povezave med spremenljivkami. V magistrskem delu je podan primer aktivnega učenja grafov.
Ključne besede: naravoslovni postopki, grafi, 2. triletje osnovne šole, aktivno učenje grafov
Objavljeno: 24.08.2018; Ogledov: 699; Prenosov: 16
Celotno besedilo (2,54 MB) |
9. Neodvisna dominacija na grafihNina Črešnjevec, 2018, magistrsko delo Opis: V magistrskem delu obravnavamo različne tipe dominacij in sicer dominantno število, neodvisnostno število, neodvisno dominantno število in zgornje dominantno število. Neodvisno dominantno število je raziskano na različnih družinah grafov kot tudi na različnih grafovskih produktih.
V prvem delu magistrske naloge smo navedli vse pojme, trditve, izreke, ki jih potrebujemo za razumevanje glavnega problema magistrske naloge. Predstavimo tudi različne razrede grafov in različne dominacije v grafih.
V drugem poglavju obravnavamo različne meje neodvisnega dominantnega števila. Predstavljene so splošne meje, ki veljajo na različnih družinah grafov in meje, ki veljajo za dvodelne grafe.
Tretje poglavje pa se nanaša na neodvisno dominantno število krepkega, korenskega in kartezičnega produkta. Za nekatere od teh produktov smo prikazali tudi rezultate o neodvisnostnem številu in dominantnem številu.
Ključne besede: dominantno število, neodvisno dominantno število, neodvisnostno število, dominantno popolni grafi, dobro pokriti grafi, grafovski produkti
Objavljeno: 13.07.2018; Ogledov: 509; Prenosov: 72
Celotno besedilo (1,30 MB) |
10. Diskretna matematikaAleksandra Tepeh, Riste Škrekovski, 2018, univerzitetni, visokošolski ali višješolski učbenik z recenzijo Opis: Učbenik je namenjen študentom visokošolskega študija računalništva in infor- matike. Predstavlja uvod v izbrana poglavja iz matematike, ki so potrebna za razumevanje in reševanje problemov, ki se pojavljajo v računalništvu. Poleg izjavnega računa, relacij in teorije grafov, ki sodijo v področje diskretne matematike, učbenik zajema tudi poglavji o geometrijskih vektorjih in matrikah. Poleg teoretične obravnave snovi učbenik vsebuje veliko zgledov za lažje razumevanje, kakor tudi naloge s postopki in rešitvami.
Ključne besede: matematika, izjavni račun, matrike, vektorji, relacije, grafi, učbeniki
Objavljeno: 12.04.2018; Ogledov: 3047; Prenosov: 1305
Celotno besedilo (9,41 MB)
Gradivo ima več datotek! Več...
|
