Euler, programček
za teorijo grafov

Vladimir Batagelj, Matjaž Zaveršnik
Univerza v Ljubljani, FMF, Oddelek za matematiko
Izobraževalna delavnica
Jadranska 19, 1000 Ljubljana

     

Programčki v Javi

Z uveljavljanjem WWW po letu 1993 se vse več izobraževalnih izdelkov pojavlja tudi v obliki omrežnih sestavkov. žal so ti pogosto le omrežne izdaje svojih papirnatih predhodnikov ali pa vsaj globoko zakoreninjeni v papirnati izkušnji. Uporaba povezav med deli besedila in z drugimi sestavki, uporaba barv ter vključevanje slik, zvoka, risank in videa pravzaprav le spravi v skupni okvir stvari, ki smo jih prej uporabljali ločeno - brez računalnika. Seveda lahko to sedaj počnemo udobneje in hitreje (, če ni težav z zvezo :-).

Bistveno novost prinaša uporaba programskih rešitev v jezikih, ki dopolnjujejo HTML, Java, JavaScript, VRML, ActiveX. Te vnašajo v omrežne sestavke živost in prilagodljivost uporabniku. Toda, za uporabo teh možnosti je treba znati programirati. Ali res? Res je, nekdo mora to narediti - vendar ne nujno pisec sestavka. Za posamezna vsebinska področja lahko programerji pripravijo ustrezne programčke v Javi, predloge v Javascriptu, prostorske opise v VRMLju, ki jih nato pisci sestavkov vključujejo v svoje stvaritve. To je razmeroma enostavno. Poglejmo, kako to storimo s programčki (applets) v Javi.

Programček napisan v Javi najprej prevedemo. V omrežni sestavek ga vključimo z značko <APPLET>

<APPLET CODE="ClassFileName" CODEBASE="ClassFileDirectory" ARCHIVE="archiveFile" ALT="altText" MAYSCRIPT ALIGN="LEFT"|"RIGHT"|"TOP"|"ABSMIDDLE"|"ABSBOTTOM"| "TEXTTOP"|"MIDDLE"|"BASELINE"|"BOTTOM" NAME="value" HEIGHT="height" WIDTH="width" HSPACE="horizMargin" VSPACE="vertMargin"> <PARAM ...> </APPLET> Z obveznim določilom CODE povemo, kateri programček vključujemo; z določilom CODEBASE povemo, kje (na katerem področju) se nahaja; obvezna WIDTH in HEIGHT določata pravokotnik v sestavku namenjen prikazu dejavnosti programčka. Podatke posredujemo programčku z značkami <PARAM NAME="paramName" VALUE="value">.

Poglejmo si primer. Rok Dremelj je za svoje diplomsko delo napisal programček Funkcije, ki omogoča vključevanje risanja funkcij v omrežne sestavke - od slik vnaprej izbranih funkcij, slik funkcij iz izbranih družin, do funkcij, ki jih določi bralec. Ta programček lahko priredimo za proučevanje trigonometrijskih funkcij z zahtevo:

<APPLET CODE=Funkcije.class WIDTH=610 HEIGHT=300> <PARAM NAME=k VALUE=1> <PARAM NAME=n VALUE=0> <PARAM NAME=funkcija1 VALUE=sin(k*x+n*PI)> <PARAM NAME=funkcija2 VALUE=cos(k*x+n*PI)> <PARAM NAME=funkcija3 VALUE=tg(k*x+n*PI)> <PARAM NAME=funkcija4 VALUE=ctg(k*x+n*PI)> <PARAM NAME=oznake VALUE=kotne> <PARAM NAME=razpon VALUE=2> <PARAM NAME=visina VALUE=300> <PARAM NAME=sirina VALUE=610> </APPLET>

Vzoren zgled tovrstnih programčkov je Geometry, s katerim je njegov avtor David E. Joyce opremil z živimi slikami celotne Evklidove Elemente; študentka pedagoške matematike Irena Bržan pa ga je uporabila pri pripravi teme Eulerjeva premica in krožnica devetih točk.

Programček Euler

Za podporo sestavkov o grafih in omrežjih smo se odločili sestaviti programček EulerGT, poimenovan po začetniku teorije grafov, švicarskem matematiku Leonhardu Eulerju (1707 - 1783); GT prihaja iz Graph Theory. V tekoči različici programčka bo, ko bo dokončana, mogoče nadzorovati njegovo delovanje z naslednjimi parametri: Lastnosti točk in povezav lahko določimo v ustreznih seznamih, tako da jih navedemo v oglatih oklepajih. Če opis lastnosti stoji samostojno, velja za vse nadaljnje točke/povezave; če pa stoji za imenom točke/povezave, velja samo zanjo. Trenutno so predvidene naslednje lastnosti:

Lastnosti točk: x: koordinata x; y: koordinata y; w: širina točke; h: višina točke; s: oblika točke (circ, rect); ic: barva notranjosti; bc: barva robu; bw: debelina robu; ime funkcije: vrednost funkcije; URL: naslov.
Lastnosti povezav: w: debelina črte; c: barva črte; ime funkcije: vrednost funkcije; s: oblika črte (line, arc(r), break(x,y)); p: lega puščice na usmerjeni povezavi (med 0 in 100).

Urejanje grafa poteka pretežno z miško. Pri delu s točkami uporabljamo levi, s povezavami pa desni gumb. Z običajnim klikom označimo točko/povezavo, s klikom in premikom jo prestavimo, z dvojnim klikom pa dobimo izpis njenih lastnosti. Če poleg držimo še tipko SHIFT, lahko označimo po več točk/povezav, vse ostale operacije potekajo na označeni skupini. Če pri kliku držimo tipko CTRL, lahko dodamo novo točko oziroma nove povezave z začetki v označenih točkah. Z uporabo tipke ALT lahko točke in povezave tudi brišemo.

S programčkom EulerGT bo mogoče podpreti vsaj naslednja opravila: prikaz slike grafa; preoblikovanje slike grafa, npr. ali je graf ravninski?; ustvarjanje / popravljanje grafa, npr. dualni graf; določanje podgrafov, komponent povezanosti, prirejanj, ...; določanje sprehodov (Eulerjev, Hamiltonov problem); barvanje točk / povezav grafa; ugotavljanje izomorfizma grafov; določanje najcenejšega vpetega drevesa, najcenejše poti, ...

V okrnjeni različici programčka EulerGT, ki ga najdemo na naslovu
http://educa.fmf.uni-lj.si/izodel/dela/Euler/
že lahko zastavimo vprašanje: Ali je dani graf ravninski?

<applet code=EulerGT width=300 height=300> <param name=bgcolor value=yellow> <param name=coordinates value=random> <param name=vertices value="1;2;3;4;5;6;7"> <param name=edges value="1-2;1-3;1-4;1-5;2-4;2-5;2-7;3-4;3-6;4-7;5-6;6-7"> </applet> EulerGT nam nariše naključno sliko danega grafa (leva stran slike), ki jo lahko s premikanjem točk predelamo v ravninski prikaz danega grafa (desna stran slike) - graf je ravninski.

Omrežna izvedba tega prispevka je dosegljiva na
http://vlado.fmf.uni-lj.si/pub/conf/MIRK.98/