Risanje grafov kot optimizacijski problem Recimo, da bi radi graf narisali tako, da bi posameznim vozliščem grafa priredili neke točke v ravnini, povezave pa bi potem predstavili z daljicami med temi točkami. Kako izbrati koordinate točk? Eden od načinov je, da definiramo neko funkcijo, ki poskusa na podlagi koordinat oceniti videz narisanega grafa, in potem izberemo koordinate tako, da je vrednost te funkcije čim 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 točk s premicami Mislimo si optimizacijski problem, pri katerem je dana množica točk v ravnini, mi pa bi radi izbrali neko množico premic, tako da bo vsaka točka ležala na vsaj eni od teh premic in da bo število premic čim manjše. Izkaže se, da je ta problem NP-težak, lahko pa poskusimo s požresnim algoritmom priti do približnih (čeprav ne optimalnih) rešitev. Predstavil bom nekaj razpostavitev točk, pri katerih se požresni algoritem odreže še posebej slabo.