Graph Theory Exercise Environment
Name
Heiki Pärn
Abstract
In Elements of Discrete Mathematics (MTAT.05.109) course various programs are used for teaching. Currently there is no program for creating and solving graph theory exercises. The purpose of this Bachelor’s thesis was to create a prototype for graph theory exercise environment. Only undirected graphs are supported in the prototype and there are six types of exercises:
1. drawing a graph based on a given adjacency matrix,
2. constructing an adjacency matrix based on a given graph,
3. drawing a complete graph,
4. drawing a complement graph of a given graph,
5. constructing a degree sequence based on a given graph,
6. drawing a graph based on a given degree sequence.
Three panels are used in different combinations for these six exercises: graph panel, matrix panel and degree sequence panel. They are used to create and solve exercises.
When creating an exercise there are constraints to prevent incorrect or empty exercises. When solving the exercises the program checks for different types of errors. All errors are recorded in the file and can be reviewed later.
One of the problems encountered was that a suitable algorithm had to be found to check whether a degree sequence is graphical or not. This problem was solved using the Erdős-Gallai theorem.
In the future it is possible to add support for directed graphs. New exercise types can also be added.
Graduation Thesis language
Estonian
Graduation Thesis type
Bachelor - Information Technology
Supervisor(s)
Rein Prank
Defence year
2013