Analysis on graph-based tasks in informatics contests

Abstract

The main purpose of this paper is to analyse the solution of graph-based tasks from the 2010–2014 informatics contest “Bebras”. The graph theory is not a compulsory subject in the Lithuanian curricula, but it is very interesting in the daily life. A lot of graph-based tasks are in the international informatics contest, and they are appointed for pupils of all ages. The analysis shows that the tasks cover various topics of graph theory: introduction to the graph concept, the shortest path problem, the binary tree, the depth-first search and breadth-first search, the travelling salesman problem and other algorithms. The most popular graph-based tasks are related to the path search. There are a lot of very attractive tasks in the “Bebras” contest, and this can be one of the non-formal ways to present the graph theory to pupils.