APPLICATION OF GRAPH MODELS IN SOLVING PRACTICAL PROBLEMS OF EDUCATION AND SPORT

Abstract

The article is a generalization of some of the author's works, prepared by him both individually
and in collaboration with colleagues. The article shows how graph theory can be applied, it would
seem, in such diverse areas as education and sports. In the first case, the graph model is used to formulate
and solve the problem of compiling optimal test tasks (tickets). It is formulated as a problem of cutting
(partitioning) the graph G (N, R) into subgraphs. The original graph G(N, R) is divided into a given
number K of subgraphs where the same topic. The peculiarities of the formulation of the given problem
give rise to many heuristic algorithms for its solution. The following heuristic is considered in the article:
each test task is formed sequentially, and each next question is placed in the current test task if its
score is the closest to the relative value of the difference between the average complexity of test tasks
and the total complexity of those questions that are already included in this test task, to the amount of
questions left to include in the task. Algorithms and results of their software implementations are presented,
with the help of which studies were carried out on the optimal formation of test tasks designed to
control the knowledge of trainees. Various heuristics are analyzed that allow optimization of test tasks.
In the second case, it is shown that tournament tables for sporting events can also be represented by
graph models. Formally, the task of drawing lots, as in the case of the formation of test tasks, is reduced
to the task of splitting the graph into subgraphs, each of which will correspond to one of the groups in
the tournament table. In addition, each vertex of the graph corresponds to the rating of a certain participant
in the tournament. The edges of the graph show the relationship between the participants – the
presence of an edge indicates that the corresponding participants are representatives of the same association
or club. Based on these models, descriptions of the developed algorithms and the results of their
software implementations for the optimal formation of tournament tables used in competitions on the
example of table tennis are given. Heuristics are analyzed for one- and two-criteria optimization of
tournament tables construction. The commonality and continuity in the algorithms for the formation of
tournament tables and the sequential distribution of questions in test tasks is to use not only graph models,
but also the same analytical relationships to formalize the heuristics used.