Разобрана задача сортировки данных, отношение порядка между которыми описано в виде отношения смежности вершин на произвольном графе. Выделены подзадачи и вопросы, относящиеся к «окрестности» проблемы; их решение представляет собой своеобразные уровни «погружения» в решение общей задачи. Обсуждены алгоритмы решения отдельных подзадач для графов специального вида, а также различные подходы к решению проблемы сортировки в общем случае. Задача сортировки такого типа предлагалась на Кубке международной школы ISI-Junior по спортивному программированию в июле 2019 года (г. Иннополис).
The problem of sorting data is analyzed, the order relation between which is described as the adjacency relation of vertices on an arbitrary graph. Subtasks and issues related to the ‘neighborhood‘ of the problem are highlighted; their solution is the level of ‘immersion‘ in the solution of the general problem. Algorithms for solving individual subtasks for graphs of a special kind are discussed, as well as various approaches to solving the sorting problem in the general case. A sorting task of this type was proposed at the ISI-Junior School Programming Cup in July 2019 (Innopolis).
The authors declare that there are no conflicts of interest present.