Romana | English


2007 | 2006 | 2005 | 2004

Minimum spanning trees
2nd Prize - Siveco Cup 2005
Graph theory - a discipline with numerous practical applications - is most of the times a difficult subject for students.
The problem of determining a minimum spanning tree is one of the problems having multiple economical applications. That's why we introduced this problem starting from two of its well-known applications - building a computer network with minimum cost and rebuilding roads in a county with minimum cost.
Afterwards we presented the problems using graph theory terminology, defining necessary concepts and we presented two algorithms for minimum spanning trees: Kruskal algorithm and Prim algorithm.

Minimum cost paths in graphs
Honorable Mention - Siveco Cup 2005
Another major topic in graph theory is the problem of determining minimum cost paths in graphs.
In this educational software we present this problems starting with a familiar practical application (determining minimum cost for flying from one airport to another). Afterwards we translated the problems using graph terminology and presented 3 fundamental algorithms for solving the problem: Dijkstra, Roy-Floyd and Belman-Ford.


© Emanuela Cerchez 2004