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.