| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 10
First pagePrevious page1Next pageLast page
1.
3-BARVANJE GRAFOV IN OPTIMIZACIJA Z ROJI DELCEV
Aleš Krauser, 2009, undergraduate thesis

Abstract: Optimizacija z roji delcev je relativno nova evolucijska tehnika, ki je bila prvotno razvita za reševanje zveznih problemov. Kasneje so se pojavile različne izvedbe za reševanje diskretnih problemov. Na začetku se seznanimo z osnovno in diskretno optimizacijo z roji delcev. Nato spoznamo parametre, ki nastopajo v optimizaciji z roji delcev. Opišemo problem 3-barvanja grafov, ki smo ga izbrali kot diskretni problem za izvajanje optimizacije z roji delcev. Temu sledi opis znanih tradicionalnih in evolucijskih algoritmov za reševanje problema 3-barvanja grafov. Nato predstavimo dva pristopa reševanja tega diskretnega problema z optimizacijo z roji delcev. Na koncu primerjamo rezultate, ki smo jih dobili z optimizacijo z roji delcev z rezultati, ki so dobljeni z hibridnim samo-prilagodljivim evolucijskim algoritmom.
Keywords: optimizacija z roji delcev, 3-barvanje grafov, hibridno samo-prilagodljivi evolucijski algoritem
Published: 02.10.2009; Views: 2358; Downloads: 140
.pdf Full text (1,37 MB)

2.
DINAMIČNO BARVANJE GRAFOV
Tjaša Grahornik, 2012, undergraduate thesis

Abstract: V diplomskem delu je predstavljeno dinamično barvanje grafov. V uvodnih poglavjih so predstavljeni osnovni pojmi iz teorije grafov, ki so pomembni za razumevanje diplomskega dela. Pogledali si bomo kakšno je dinamično kromatično število za polne grafe, drevesa in cikle. V nalogi so opisane znane zgornje meje za dinamično kromatično število. Primerjali smo kromatično število in dinamično kromatično število za normalne grafe in regularne grafe. Ugotovili smo, da je razlika med dinamičnim kromatičnim številom in kromatičnim številom poljubno velika za nekatere grafe. Del diplomske naloge bomo posvetili tudi dinamičnemu barvanju kartezičnega produkta dveh grafov ter zaključili s posplošitvijo dinamičnega barvanja.
Keywords: dinamično barvanje grafov, zgornje meje, kartezični produkt, posplošitev dinamičnega barvanja
Published: 11.10.2012; Views: 1120; Downloads: 114
.pdf Full text (586,39 KB)

3.
How good can ants color graphs?
Aleksander Vesel, Janez Žerovnik, 1998

Abstract: 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.
Keywords: matematika, teorija grafov, barvanje grafov, postopek zaporednega barvanja, algoritem mravlje, Petford-Welsh, RLF, mathematics, graph theory, graph coloring, ants algorithm, Petford-Welsh, RLF
Published: 10.07.2015; Views: 541; Downloads: 21
URL Link to full text

4.
Simpler multicoloring of triangle-free hexagonal graphs
Ignasi Sau Walls, Petra Šparl, Janez Žerovnik, 2012, published scientific conference contribution

Abstract: 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).
Keywords: 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
Published: 10.07.2015; Views: 537; Downloads: 57
URL Link to full text

5.
2-local distributed algorithms for generalized coloring of hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, published scientific conference contribution

Abstract: 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.
Keywords: 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
Published: 10.07.2015; Views: 623; Downloads: 69
URL Link to full text

6.
7.
Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Petra Šparl, Janez Žerovnik, 2009, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, homomorfizem, H-barvanje, heksagonalen graf brez trikotnikov, mathematics, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Published: 10.07.2015; Views: 504; Downloads: 15
URL Link to full text

8.
Hevristični algoritem za 3-barvanje grafov
Luka Arnečič, 2015, master's thesis

Abstract: 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].
Keywords: barvanje grafov, algoritmi na grafih, diskretni algoritmi, hevristike
Published: 15.02.2016; Views: 861; Downloads: 77
.pdf Full text (860,06 KB)

9.
Obravnava barvanj grafov in tetivnih grafov v srednješolskem izobraževanju
Jasmina Ferme, 2016, master's thesis

Abstract: 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.
Keywords: Barvanje vozlišč grafov, tetivni grafi, grafi intervalov, teorija grafov v srednješolskem izobraževanju.
Published: 10.08.2016; Views: 791; Downloads: 230
.pdf Full text (3,29 MB)

10.
Harmonično barvanje dreves
Luka Žnidarič, 2018, master's thesis

Abstract: 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.
Keywords: drevesa, barvanje grafov, harmonično barvanje
Published: 03.10.2018; Views: 287; Downloads: 38
.pdf Full text (822,40 KB)

Search done in 0.26 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica