Novice

SEMINAR MARA

V ponedeljek, 10.11.2008, bosta ob 16. uri  v  mali predavalnici  Fakultete za matematiko, naravoslovje in inforamcijske tehnologije Univerze na Primorskem, Glagoljaška 8,  Koper predavanji v okviru skupnega SEMINARJA ZA MATEMATICNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in računalništvo UP FAMNIT, Oddelka za matematiko in računalništvo UP PINT, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.
Dnevni red:

16:00 -- 17:00

Predavatelj: Martin Milanič

Naslov: O problemu neodvisne množice grafa v hereditarnih grafovskih razredih

Povzetek:

Neodvisna množica v grafu je množica paroma nepovezanih vozlišč. Problem neodvisne množice sprašuje po moči največje neodvisne množice v danem grafu. Ta problem je NP-poln ne samo v splošnem, ampak tudi za posebne grafovske razrede, med drugim za ravninske grafe in za grafe maksimalne stopnje največ tri.

Za številne druge grafovske razrede je problem rešljiv v polinomskem času. Mednje spadajo dvodelni grafi, perfektni grafi in grafi, v katerih nobeno vozlišče nima treh paroma nepovezanih sosedov. Metode, ki vodijo do polinomskih algoritmov na posebnih grafih, so v splošnem zelo raznolike.

Osredotočili se bomo na dve metodi: na modularno dekompozicijo in na dekompozicijo po prereznih klikah. Predstavili bomo nekaj novejših rezultatov, dobljenih s pomočjo teh dveh metod. Med drugim bomo opisali družino algoritmov, ki v polinomskem času rešijo problem neodvisne množice na nekaterih ravninskih grafih.

17:00 -- 17:30

Predavatelj: Kati Rozman

Naslov predavanja: Problem maksimalne klike na neusmerjenih grafih

Povzetek:

Klika grafa je polni podgraf, kjer med vsakim parom tock poteka povezava. Problem maksimalne klike je problem poiskati v danem neusmerjenem grafu   kliko z najvecjim stevilom tock. Problem uvrscamo med NP-težke probleme. Algoritmi za iskanje maksimalne klike se uporabljajo v matematiki, bioinformatiki, torej povsod tam, kjer lahko iscemo podobnosti med strukturami.

Maximum clique problem of an undirected graph

A clique is a subset S of vertices in a graph such that each pair of vertices in is S is connected by an edge. The maximum clique problem is the problem of finding in a given graph the clique with the largest number of vertices. It is NP-hard problem. The algorithms for finding a maximum clique are used in mathematics, bioinformatics, where their main application is to search for similarity between structures.

17:30 -- 18:00

Predavatelj: Mojca Leskovec Meharich

Naslov predavanja: Uvod v uporabo graf-teoretičnih matrik v kemiji

Povzetek:

Predstavitev klasifikacije in sedanjih raziskav na področju graf-toretičnih matrik, ki jih uporabljajo v kemiji. Na enem mestu, kot spletni učbenik, so zbrane in klasificirane graf-teoretične matrike. Le-te so uporabne v mnogih aplikacijah: v generiranju molekularnih deskriptorjev, v generiranju in preštevanju izomerov ter valence kemijskih struktur, za izgradnjo in filtracijo virtualne kombinatorične knjižnice, ki je potrebna za racionalno pripravo želenih spojin.


Introduction to graph-theoretical matrices in chemistry


Presentation and classification of graph-theoretical matrices, that are frequently encountered in chemical graph theory. The graph-theoretical matrices are convenient devices for the algebraic representation of graphs âEUR" they allow numerical handling of graphs. Most of the graph-theoretical matrices are used as sources of molecular descriptors usually referred to as topological indicies âEUR" which have found considerable application in structure-property-activity modeling, usually abbreviated as QSPR (quantitative structure-property relationship) and QSAR (quantitative structure-activity relationship). Graph-theoretical matrices have also been used however for many other purposes in chemistry.



Vabljeni!