[Solomonov Seminar] 145. Solomonov seminar

[Marko Grobelnik]

Vabim vas na 145. Solomonov seminar, ki bo v torek,
13. aprila 2004 ob 13:00 uri v Veliki predavalnici IJS.
Posnetki preteklih seminarjev so na http://solomon.ijs.si/ 

Na tokratnem seminarju bo Janez Brank predstavil resitvi dveh 
zanimivih problemov: (1) Risanje grafov kot optimizacijski 
problem (2) Pokrivanje tock s premicami. 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Janez Brank, IJS:
  Dva problema: lepo risanje grafov in pokrivanje tock s premicami

Risanje grafov kot optimizacijski problem
 
Recimo, da bi radi graf narisali tako, da bi posameznim vozliscem 
grafa priredili neke tocke v ravnini, povezave pa bi potem predstavili 
z daljicami med temi tockami.  Kako izbrati koordinate tock?  
Eden od nacinov je, da definiramo neko funkcijo, ki poskusa na 
podlagi koordinat oceniti videz narisanega grafa, in potem izberemo 
koordinate tako, da je vrednost te funkcije cim manjsa.  Predstavil bom 
funkcijo, ki sta jo predlagala Davidson in Harel leta 1996 in se se kar 
dobro obnese na majhnih grafih.  Onadva sta jo minimizirala s 
simuliranim ohlajanjem, jaz pa sem jo poskusil malo predelati, 
da je postala odvedljiva, in sem jo minimiziral z gradientnim spuscanjem.
 
Pokrivanje tock s premicami
 
Mislimo si optimizacijski problem, pri katerem je dana mnozica tock 
v ravnini, mi pa bi radi izbrali neko mnozico premic, tako da bo vsaka 
tocka lezala na vsaj eni od teh premic in da bo stevilo premic cim manjse.  
Izkaze se, da je ta problem NP-tezak, lahko pa poskusimo s pozresnim 
algoritmom priti do pribliznih (ceprav ne optimalnih) resitev.  Predstavil 
bom nekaj razpostavitev tock, pri katerih se pozresni algoritem odreze 
se posebej slabo.