ПРИМЕНЕНИЕ ГРАФОВЫХ МОДЕЛЕЙ ПРИ РЕШЕНИИ ПРАКТИЧЕСКИХ ЗАДАЧ ОБРАЗОВАНИЯ И СПОРТА

Аннотация

Статья является обобщением некоторых работ автора, подготовленных им как ин-
дивидуально, так и в соавторстве с коллегами. В статье показано, как теория графов
может применяться, казалось бы, в таких различных областях как образование и спорт.
В первом случае графовая модель использована для формулировки и решения задачи со-
ставления оптимальных тестовых заданий (билетов). Задача составления оптимальных
тестовых заданий формулируется как задача разрезания (разбиения) графа G(N,R) на
подграфы ( , ). i i i G N R Исходный граф G(N, R) разбивается на заданное число K подграфов
( , ), i i i G N R где iK, так, чтобы сложность каждого задания была одинакова и в каждом
задании находилось минимальное число вопросов из одной и той же темы. Особенности
формулировки приведенной задачи порождают множество эвристических алгоритмов ее
решения. В статье рассматривается следующая эвристика: каждое тестовое задание
формируется последовательно, а каждый очередной вопрос помещается в текущее тес-
товое задание, если его оценка является ближайшей к относительной величине разности
средней сложности тестовых заданий и суммарной сложности тех вопросов, которые
уже включены в данное тестовое задание, к сумме вопросов, которое осталось включить в
задание. Представлены алгоритмы и результаты их программных реализаций, с помощью
которых проведены исследования по оптимальному формированию тестовых заданий,
предназначенных для контроля знаний обучаемых. Анализируются различные эвристики,
позволяющие осуществлять оптимизацию тестовых заданий. Во втором случае показано,
что турнирные таблицы для проведения спортивных мероприятий также могут быть
представлены графовыми моделями. Формально задача жеребьевки, как и в случае форми-
рования тестовых заданий, сводится к задаче разбиения графа на подграфы, каждый из
которых будет соответствовать одной из групп в турнирной таблице. При этом каждая
вершина графа соответствует рейтингу определенного участника турнира. Ребрами гра-
фа отображаются отношения между участниками – наличие ребра говорит о том, что
соответствующие участники являются представителями одной ассоциации или клуба.
Опираясь на эти модели, приводятся описания разработанных алгоритмов и результаты
их программных реализаций по оптимальному формированию турнирных таблиц, исполь-
зуемых при проведении соревнований на примере настольного тенниса. Анализируются
эвристики для одно и двухкритериальной оптимизации построения турнирных таблиц.
Общность и преемственность в алгоритмах формирования турнирных таблиц и последо-
вательного распределения вопросов в тестовых заданиях проявляется в использовании не
только графовых моделей, но и одних и тех же аналитических соотношений, для формали-
зации используемых эвристик.