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.
References
approach]. Moscow: Izd-vo «M r», 1978, 432 p.
2. Ore O. Teoriya grafov [Graph theory]. 2nd ed. Moscow: Nauka, Glav. red. Fizmat. lit-ry,
1980, 336 p.
3. Nechepurenko M.I., Popkov V.K., Maynagashev S.M. i dr. Algoritmy i programmy resheniya
zadach na grafakh i setyakh [Algorithms and programs for solving problems on graphs and
networks]. Novosibirsk: Sib. otd-nie, 1990, 515 p.
4. Bashmakov A.I., Bashmakov I.A. Razrabotka komp'yuternykh uchebnikov i obuchayushchikh
system [Development of computer textbooks and training systems]. Moscow: Informatsionnozdatel'sk
y dom «F l n'», 2003, 616 p.
5. Mayorov A.N. Teoriya i praktika sozdaniya testov dlya sistemy obrazovaniya [Theory and
practice of creating tests for the education system]. Moscow: Intellekt-tsentr, 2001, 296 p.
6. Radchikov N.P. Testy proverki znaniy: etapy razrabotki [Knowledge testing tests: stages of
development]. Minsk: RIVSh, 2007, 30 p.
7. Erokhin A.L., Kol'chenko A.V., Patrakh T.E., Chikina V.A. Programmnyy kompleks dlya
generatsii komp'yuternykh testiruyushchikh sistem [A software package for generating computer
testing systems], Obrazovanie i virtual'nost': Sb. nauchnykh trudov 6-y Mezhdunarodnoy
konferentsii Ukrainskoy assotsiatsii distantsionnogo obrazovaniya [Education and virtuality:
A collection of scientific papers of the 6th International Conference of the Ukrainian Association
of Distance Education]. Khar'kov – Yalta: UADO, 2002, pp. 323-327.
8. Erokhin A.L. Kol'chenko A.V., Strukova A.V. Ispol'zovanie testiruyushchikh sistem v
uchebnykh zavedeniyakh i prakticheskikh podrazdeleniyakh OVD [The use of testing systems
in educational institutions and practical departments of the Department of Internal Affairs],
Pravo i bezpeka [Law and security], 2002, No. 3, pp. 128-130.
9. Glushan' V.M., Lipalo N.N, Malyutin V.A. Optimizatsiya testovykh zadaniy pri kontrole znaniy
[Optimization of test tasks in the control of knowledge], Vestnik Taganrogskogo
gosudarstvennogo pedagogicheskogo instituta. Estestvennye nauki [Bulletin of the Taganrog
State Pedagogical Institute. Natural sciences], 2007, No. 1, pp. 72-76.
10. Glushan' V.M., Afanas'ev A.Yu. Algoritmy optimizatsii testovykh zadaniy [Algorithms for
optimization of test tasks], Vestnik Taganrogskogo gosudarstvennogo pedagogicheskogo
instituta. Fiziko-matematicheskie i estestvennye nauki [Bulletin of the Taganrog State Pedagogical
Institute. Physical, mathematical and natural sciences], 2010, No. 1, pp. 128-136.
11. Afanas'ev A.Yu., Glushan' V.M., Karelin V.P. Issledovanie algoritmov optimizatsii testovykh
zadaniy [Research of algorithms for optimization of test tasks], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12, pp. 203-211.
12. Glushan' V.M. Kriterial'nye osobennosti optimal'nogo formirovaniya turnirnykh tablits [Criteria
features of optimal formation of tournament tables], Tr. Kongressa po intellektual'nym
sistemam i informatsionnym tekhnologiyam «IS&IT'14». Nauchnoe izdanie v 4-kh t. T. 1 [Proceedings
of the Congress on Intelligent Systems and Information Technologies "IS&IT'14".
Scientific edition in 4 vol. Vol. 1]. Moscow: Fizmatlit, 2014, pp. 446-453.
13. Glushan' V.M, Kazharov A.A., Ponomarev V.K. Metody optimal'nogo avtomatizirovannogo
formirovaniya turnirnykh tablits [Methods of optimal automated formation of tournament tables],
Programmnye produkty i sistemy. Mezhdunarodnyy nauchno-prakticheskiy zhurnal
[Software products and systems. International Scientific and Practical Journal], 2015, No. 3
(111), pp. 226 -232.
14. Glushan' V.M., Zubritskiy A.V. Polnoperebornyy variant formirovaniya turnirnykh tablits
[A full-fledged version of the formation of tournament tables], Tr. Kongressa po
intellektual'nym sistemam i informatsionnym tekhnologiyam «IS&IT'16». Nauchnoe izdanie v
3-kh t. T. II [Proceedings of the Congress on Intelligent Systems and Information Technologies
"IS&IT'16". Scientific edition in 3 vol. Vol. II]. Taganrog: Izd-vo YUFU 2016, pp. 193-199.
15. Glushan' V.M., Zubritskiy A.V. Algoritm razbieniya mnozhestva po ego nomeru na
sovokupnost' ravnomoshchnykh podmnozhestv [Algorithm for splitting a set by its number into
a set of equally powerful subsets], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU.
Engineering Sciences], 2018, No. 4 (198), pp. 59-65.
16. Glushan' V.M., Afanas'ev A.Yu. Optimal'nyy raspredelitel' testovykh zadaniy. Svidetel'stvo o
gosudarstvennoy reg strats dlya EVM № 2010612908 [The opt mal d str butor of test tasks.
Certificate of state registration for computers No. 2010612908].
17. Glushan' V.M., Kazharov A.A. Programma optimal'nogo razmeshcheniya ob"ektov v
diskretnom pryamougol'nom prostranstve. Svidetel'stvo o gosudarstvennoy registratsii programmy
dlya EVM № 2015618325 [A program for opt mal placement of objects in a discrete
rectangular space. Certificate of state registration of the computer program No. 2015618325].
18. Glushan' V.M., Afanas'ev A.Yu., Lyashchenko N.I. Kontseptsiya sozdaniya
avtomatizirovannogo rabochego mesta (ARM) prepodavatelya [The concept of creating an automated
workplace (APM) of a teacher], Vestnik Taganrogskogo pedagogicheskogo instituta.
Fiziko-matematicheskie i estestvennye nauki [Bulletin of the Taganrog Pedagogical Institute.
Physical, mathematical and natural sciences], 2011, No. 1, pp. 108-111.
19. Glushan' V.M., Afanas'ev A.Yu., Lyashchenko N.I. Optimizatsiya vuzovskogo obrazovatel'nogo
protsessa v srede avtomatizirovannogo obucheniya i kontrolya znaniy [Optimization of the
university educational process in the environment of automated learning and knowledge control],
Vestnik Taganrogskogo pedagogicheskogo instituta. Fiziko-matematicheskie i
estestvennye nauki [Bulletin of the Taganrog Pedagogical Institute. Physical, mathematical and
natural sciences], 2011, No. 1, pp. 111-116.
20. Available at: http://www.ystok.ru/tournament/ (accessed 25August 22).
21. Available at: https://www.qrz.ru/software/category/8.html (accessed 25August 22).
22. Penov G.G, Aleksandrov A.V., Zubar' YA.S., Kizilov A.V., Mazaev K.M., Ponomarev V.K.
Nastol'nyy tennis. Sbornik materialov dlya sudey [Table tennis. Collection of materials for
judges]. Moscow, 2012.
