1. Principi modeliranja v logistiki : e-gradivo za predmetJanez Žerovnik, 2015, drugo učno gradivo Ključne besede: definicije, Eulerjevi grafi, Hamiltonovi grafi, drevesa, barvanje grafov, algoritmi, teorija grafov, logistika, učbeniki
Objavljeno v DKUM: 07.10.2024; Ogledov: 0; Prenosov: 9
 Celotno besedilo (3,66 MB)
Gradivo ima več datotek! Več... |
2. Pakirno barvanje grafa : na študijskem programu 2. stopnje MatematikaTomaž Ličina, 2021, magistrsko delo Opis: Pakirno barvanje grafe je dobro barvanje vozlišč, pri katerem sta poljubni dve vozlišči z isto barvo i na razdalji večji kot i. Pakirno kromatično število je najmanjše število barv, ki jih potrebujemo za tako barvanje grafa.
V magistrskem delu obravnavamo pakirno kromatično število nekaterih družin grafov in zvezo pakirnega kromatičnega števila z drugimi grafovskimi invariantami. Podrobneje obravnavamo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom.
V prvem delu proučujemo pakirno kromatično število na osnovnih družinah grafov, na drevesih, kartezičnih produktih grafov in na grafih Mycielskega. V naslednjem delu obravnavamo grafe z majhnimi pakirnimi kromatičnimi števili in pokažemo, da je preveriti, ali ima graf pakirno kromatično število enako 4, NP-težek problem. V tretjem delu prikažemo zvezo pakirnega kromatičnega števila z neodvisnostnim številom grafa, najmanjšim vozliščnim pokritjem grafa in maksimalno stopnjo v grafu. V zadnjem delu raziskujemo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. Poiščemo trojice naravnih števil (a,b,c) za katere obstaja graf G s kličnim številom a, kromatičnim številom b in pakirnim kromatičnim številom c.
Ključne besede: barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje
Objavljeno v DKUM: 12.01.2022; Ogledov: 880; Prenosov: 66
Celotno besedilo (613,60 KB)
Gradivo ima več datotek! Več... |
3. Harmonično barvanje drevesLuka Žnidarič, 2018, magistrsko delo Opis: Harmonično barvanje grafa je dobro barvanje njegovih vozlišč, tako da se poljuben par različnih barv pojavi na največ enem paru sosednjih vozlišč. Harmonično kromatično število grafa G je najmanjše število barv, ki jih potrebujemo za harmonično barvanje grafa G. Znano je, da je določitev harmoničnega kromatičnega števila grafa NP-težek problem. V magistrskem delu bo pokazano, da problem ostane NP-težek tudi v primeru dreves. Nadalje bodo obravnavane različne družine dreves, za katere je problem lažje rešljiv. Določene bodo natančne vrednosti harmoničnega kromatičnega števila teh dreves, v nekaterih primerih pa bo opisan tudi polinomski algoritem, ki podano drevo harmonično pobarva z želenim številom barv.
Ključne besede: drevesa, barvanje grafov, harmonično barvanje
Objavljeno v DKUM: 03.10.2018; Ogledov: 1109; Prenosov: 113
Celotno besedilo (822,40 KB) |
4. Obravnava barvanj grafov in tetivnih grafov v srednješolskem izobraževanjuJasmina Ferme, 2016, magistrsko delo Opis: V magistrskem delu obravnavamo izbrane vsebine s področja teorije grafov, te so barvanje vozlišč grafov, tetivni grafi in grafi intervalov. V prvem delu navedemo vse potrebne definicije, trditve in izreke skupaj z dokazi. Podamo več karakterizacij tetivnih grafov in grafov intervalov, kjer se osredotočamo na obravnavo z vidika presečnih grafov. Navedene vsebine tudi povezujemo in odkrivamo zveze med njimi, posvetimo se predvsem barvanju tetivnih grafov in grafov intervalov.
V drugem delu magistrskega dela podajamo primer obravnave navedenih vsebin v srednješolskem izobraževanju; vključimo tudi obravnavo vsebine uvod v teorijo grafov ter vsebine, ki združuje navedeno. Vsebine podajamo v obliki vsebinsko-metodičnih priprav na poučevanje, v sklopu katerih predlagamo tudi učne oblike in metode, učne pripomočke in časovni razpored aktivnosti ter navajamo matematična znanja, ki jih dijaki razvijajo tekom učnih ur. Podajamo teoretične osnove nekaterih didaktični elementov ter navajamo načela, s katerimi je poučevanje po pripravah usmerjeno in cilje, ki jih uresničuje.
Ključne besede: Barvanje vozlišč grafov, tetivni grafi, grafi intervalov, teorija grafov v srednješolskem izobraževanju.
Objavljeno v DKUM: 10.08.2016; Ogledov: 1843; Prenosov: 350
Celotno besedilo (3,29 MB) |
5. Hevristični algoritem za 3-barvanje grafovLuka Arnečič, 2015, magistrsko delo Opis: Magistrsko delo obravnava hevristični algoritem za 3-barvanje grafov, ki temelji na hibridiziranem evolucijskem algoritmu in se lahko uporabi za ugotavljanje dobre 3-obarvljivosti navadnih neusmerjenih grafov. Najprej razložimo matematične osnove problema in predstavimo algoritme, na katerih temelji naš hevristični algoritem, nato ga opišemo, na koncu pa predstavimo primerjavo hevrističnega algoritma z algoritmi uporabljenimi in opisanimi v osnovnem članku [9].
V prvem delu razložimo matematične osnove, ki so potrebne za razumevanje problema dobrega 3-barvanja grafov in predstavimo osnovne zasnove algoritmov, na katerih temelji hevristični algoritem.
V drugem delu predstavimo hevristični algoritem po komponentah ter podatkovne strukture, ki so uporabljene v hevrističnem algoritmu. Vsako komponento algoritma natančno opišemo in predstavimo idejo, za katero je bila uporabljena.
V tretjem delu predstavimo primerjavo hevrističnega algoritma z algoritmi, uporabljenimi in opisanimi v osnovnem članku [9].
Ključne besede: barvanje grafov, algoritmi na grafih, diskretni algoritmi, hevristike
Objavljeno v DKUM: 15.02.2016; Ogledov: 2128; Prenosov: 858
Celotno besedilo (860,06 KB) |
6. Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graphPetra Šparl, Janez Žerovnik, 2009, izvirni znanstveni članek Opis: Problem odločanja ali obstaja homomorfizem iz poljubnega grafa ▫$G$▫ v dani graf ▫$H$▫ je bil že večkrat proučevan in se je izkazal za zelo težkega. Hell in Nešetril sta dokazala, da je odločitveni problem NP-poln, če ▫$H$▫ ni dvodelen graf. V članku je obravnavan poseben problem, kjer je ▫$G$▫ poljuben heksagonalen graf brez trikotnikov, ▫$H$▫ pa Kneserjev graf ali njegov inducirani podgraf. Podana je esplicitna konstrukcija, ki dokazuje obstoj homomorfizma iz poljubnega heksagonalnega grafa brez trikotnikov v Petersenov graf brez ene točke.
Ključne besede: matematika, teorija grafov, homomorfizem, H-barvanje, heksagonalen graf brez trikotnikov, mathematics, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 1263; Prenosov: 29
 Povezava na celotno besedilo |
7. Collins, Karen L.(1-WESL-C); Shemmer, Benjamin(1-WESL-C): Constructions of 3-colorable cores. (English summary). - SIAM J. Discrete Math. 16 (2002), no. 1,74--80 (electronic)Sandi Klavžar, 2004, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, barvanje, kromatično število, avtomorfizem, mathematics, graph theory, coloring, Chromatic number, automorphisem
Objavljeno v DKUM: 10.07.2015; Ogledov: 1054; Prenosov: 38
Povezava na celotno besedilo |
8. 2-local distributed algorithms for generalized coloring of hexagonal graphsPetra Šparl, Janez Žerovnik, 2005, objavljeni znanstveni prispevek na konferenci Opis: A 2-local distributed approximation algorithm for multicoloring of a triangle-free hexagonal graph which uses at most ▫$lceil frac{5omega(G)}{4} rceil + 3$▫ colors is presented.
Ključne besede: matematika, teorija grafov, barvanje grafov, aproksimacijski algoritem, frekvenčni načrt, ▫$k$▫-lokalen porazdeljen algoritem, mathematics, graph theory, approximation algorithms, graph coloring, frequency planning, ▫$k$▫-local distributed algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1285; Prenosov: 102
Povezava na celotno besedilo |
9. Simpler multicoloring of triangle-free hexagonal graphsIgnasi Sau Walls, Petra Šparl, Janez Žerovnik, 2012, objavljeni znanstveni prispevek na konferenci Opis: Preslikavo ▫$f colon V(G)to 2^{{1,.,n}}$▫, za katero velja ▫$|f(v)| ge p(v)$▫ za vsako točko ▫$v in V(G)$▫ in ▫$f(v) cap f(u) = emptyset$▫ za poljubni sosedi ▫$u$▫ in ▫$v$▫ grafa ▫$G$▫, imenujemo dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫. Najmanjše naravno število, za katero obstaja dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫, ▫$chi_p(G)$▫, imenujemo uteženo kromatično število grafa ▫$G$▫. Iskanje uteženega kromatičnega števila za inducirane podgrafe trikotniške mreže (imenovane heksagonalni grafi) ima aplikacije v celičnih mrežah. Uteženo kromatično število grafa ▫$G$▫, ▫$omega_p(G)$▫, je enako maksimalni uteži klike grafa ▫$G$▫, kjer utež klike predstavlja vsoto uteži njenih točk. McDiarmid in Reed (2000) sta postavila domnevo, da za poljuben heksagonalen graf brez trikotnikov velja ▫$chi_p(G) le (9/8)omega_p(G) + C$▫. V članku je podan algoritem, ki poda dobro ▫$7-[3]$▫barvanje poljubnega heksagonalnega grafa brez trikotnikov, ki aplicira neenakost ▫$chi_p(G) le (7/6)omega_p(G) + C$▫. Naš rezultat podaja krajšo alternativo induktivnega dokaza Haveta (2001) in izboljša kratek dokaz Sudepa in Vishwanathana (2005), ki sta dokazala obstoj ▫$14-[6]$▫barvanja. (Omeniti je potrebno, da v sklopu našega dokaza uporabimo izrek o štirih barvah.) Vsi koraki algoritma so linearni glede na ▫$|V(G)|$▫, razen 4-barvanje ravninskega grafa. Novi pristop lahko v prihodnje pripomore k dokazovanju domneve McDiarmida in Reeda (2000).
Ključne besede: matematika, teorija grafov, aproksimacijski algoritem, barvanje grafov, dodeljevanje frekvenc, celične mreže, mathematics, graph algorithm, graph theory, approximation algorithm, graph coloring, frequency planning, cellular networks
Objavljeno v DKUM: 10.07.2015; Ogledov: 1351; Prenosov: 89
Povezava na celotno besedilo |
10. How good can ants color graphs?Aleksander Vesel, Janez Žerovnik, 1998 Opis: V notici primerjamo algoritem Coste in Hertza, algoritem "mravlje", s postopkom zaporednega barvanja (RLF, recursive largest first) in z algoritmom tipa Petforf-Welsh. V naših poskusih je zadnji precej boljši od prvih dveh.
Ključne besede: matematika, teorija grafov, barvanje grafov, postopek zaporednega barvanja, algoritem mravlje, Petford-Welsh, RLF, mathematics, graph theory, graph coloring, ants algorithm, Petford-Welsh, RLF
Objavljeno v DKUM: 10.07.2015; Ogledov: 1566; Prenosov: 43
Povezava na celotno besedilo |
