УДК 519.1

Автоматическая генерация графов для электронных обучающих систем

Автоматическая генерация графов для электронных обучающих систем
©Зайнуллина Р. Ф., ORCID: 0000-0002-8027-3767, Казанский национальный исследовательский технический университет им. А.Н. Туполева - КАИ, г. Казань, Россия, ananasfeer@gmail.com

Аннотация. Предметом исследования является один из способов актуализации современных обучающих систем решения задач теории графов, а именно, автоматическая генерация графов. Такой подход позволит уменьшить нагрузку на базу данных обучающей системы, и без обновления банка задач в реальном времени генерировать для пользователя задачи. В ходе работы были выявлены преимущества и недостатки такого подхода. Выбран наиболее подходящий для реализации исследования способ представления графов в электронных вычислительных машинах. Выявлены и обоснованы требования к генерируемым графам и возможные способы реализации этих требований. А именно: в реализуемой программе будут генерироваться простые связные неориентированные графы. Рассмотрели важную деталь в работе с графами — обход графа при помощи алгоритма «Поиск в глубину (ширину)», в данной задаче используемый для проверки графа на связность. Приведен результат работы — программная реализация алгоритма генерации графа на языке программирования C#. В ней графы представляются списком смежности, генерируются случайно и проверяются на связность при помощи функции DFS (Depth First Search). Функция DFS является программной реализацией алгоритма «Поиск в глубину».

Ключевые слова: теория графов, обучающая система, поиск в глубину, связность графов, списки смежности.

Automatic Graph Generation for E-learning Systems
©Zainullina R., ORCID: 0000-0002-8027-3767, Kazan National Research Technical University named after A. N. Tupolev - KAI, Kazan, Russia, ananasfeer@gmail.com

Abstract. The subject of the research is one of the ways of updating modern training systems for solving problems of graph theory, namely, automatic generation of graphs. This approach will reduce the load on the training system database and generate tasks for the user in real-time without updating the bank of tasks. In the course of the work, the advantages and disadvantages of this approach were identified. The most suitable method for the implementation of the research was chosen to represent graphs in electronic computers. The requirements for generated graphs and possible ways of implementing these requirements are identified and substantiated. Namely: in the implemented program, simple connected undirected graphs will be generated. We considered an important detail in working with graphs — graph traversal using the “Depth (width) search” algorithm, which in this task is used to check the graph for connectivity. The result of the work is presented — a software implementation of the graph generation algorithm in the C# programming language. In it, graphs are represented by an adjacency list, generated randomly, and checked for connectivity using the DFS (Depth First Search) function. DFS is a software implementation of the Depth First Search algorithm.

Keywords: graph theory, training system, depth-first search, graph connectivity, adjacency lists.

Ссылка для цитирования:

Зайнуллина Р. Ф. Автоматическая генерация графов для электронных обучающих систем // Бюллетень науки и практики. 2021. Т. 7. №6. С. 12-16. https://doi.org/10.33619/2414-2948/67/01

Cite as (APA):

Zainullina, R. (2021). Automatic Graph Generation for E-learning Systems. Bulletin of Science and Practice, 7(6), 12-16. (in Russian). https://doi.org/10.33619/2414-2948/67/01