|
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
pogosto ti 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 v Javi.
Programček napisan v Javi najprej prevedemo. V omrežni sestavek
ga vključimo z značko <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:
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:
- bgcolor: barva ozadja;
- coordinates: začetna razmestitev točk,
če koordinate niso podane (random, circular);
- vertices: seznam točk, ločenih s podpičji;
- edges: seznam neusmerjenih povezav,
ločenih s podpičji; posamezna povezava je podana
s točkama (krajiščema), ločenima s pomišljajem;
- arcs: seznam usmerjenih povezav,
ločenih s podpičji; posamezna povezava je podana
z začetno in končno točko, ločenima s pomišljajem;
- options: seznam dovoljenih operacij z grafom
(select, move, add, delete,
prop, applet, info, ...);
- functions: seznam imen funkcij nad grafom
(barvanja, podgrafi, dolzine, ...);
- test: preverjanje posameznih lastnosti;
- ime palete: seznam barv;
- labels: prikaz oznak
(on/off(vertices,
edges, arcs)).
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 pa 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?
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 -
graf je ravninski. Graf na desni strani slike pa ni ravninski.
Omrežna izvedba tega prispevka je dosegljiva na
http://vlado.fmf.uni-lj.si/pub/conf/MIRK.98/