Tasks on graphs

From IOI Wiki
Jump to: navigation, search
Pub article.png
  • Article: Tasks on graphs
  • Author(s): Krassimir Manev
  • Journal: Olympiads in Informatics 2 (2008), 90-104

Abstract: Despite missing of the topic in standard school curricula, tasks on graphs are among the most used in programming contest for secondary school students. The paper starts with fixing the used terminology. Then one possible classification of tasks on graphs is proposed. Instead of the inner logic of Graphs Theory, which is typical for some profiled textbooks, the classification approach of the general textbooks on algorithms was used. The tasks on graphs from last ten editions of the Bulgarian National Olympiad in Informatics were considered and classified in order to check the usability and productivity of the proposed classification.

Keywords: graph structures, directed and undirected graphs and multi-graphs, classification of tasks on graphs, algorithmic schemes

Download: http://www.mii.lt/olympiads_in_informatics/htm/INFOL029.htm (free)