Управляющие системы и машины, №5, 2018, стаття 2
DOI: https://doi.org/10.15407/usim.2018.05.013
Семенюта М.Ф., Шерман З.А., Дмитриев О.Н. Неполные турниры и магические типы разметок. Управляющие системы и машины. 2018. № 5. C. 13-24.
УДК 519.1
Семенюта Марина Фролівна, канд. фіз.-мат. наук, професор кафедри фізико-математичних дисциплін Льотної акад. нац. авіац. ун-ту, м. Кропивницький, пров. Ботанічний, 12, marina_semenyuta@ukr.net
Шерман Зоя Олександрівна, канд. фіз.-мат. наук, Донецький національний медичний університет, старший викладач кафедри медичної фізики та інформаційних технологій №2, E-mail: sherman.zoya@gmail.com
Дмітрієв Олег Миколайович, канд. техн. наук, завідувач кафедри льотної експлуатації, аеродинаміки і динаміки польоту Льотної акад. нац. авіац. ун-ту, м. Кропивницький, пров. Ботанічний, 12, E-mail: Dmitronik70@i.ua
Неповні турніри і магічні типи розміток
Вступ. В спортивному світі існує різноманітна кількість видів турнірів, планування яких базується на побудові графових моделей. Кожен вид турніру має свої характеристики. В даній роботі розглядаються справедливі, їм еквівалентні та врівноважені неповні турніри. Створення турнірної сітки для n команд, що грають з r опонентами для таких турнірів, рівносильно розв’язанню задачі побудови відповідної дистанційної магічної або антимагічної розмітки r-регулярного графа порядку n.
Мета статті – систематизувати основні теоретичні відомості, що відносяться до даної тематики, виділити відриті проблеми, класифікувати методи побудови графів турнірів і уніфікувати алгоритми їх опису відповідно до цієї класифікації.
Методи. Запропоновано нові алгоритми побудови графів неповних турнірів. Це дає можливість розширити коло задач з використанням математичних моделей на основі розмічених графів.
Результат. Всі методи побудови графів турнірів розбиті на три групи. До методів першої групи віднесені ті, які базуються на властивостях магічних прямокутників, в тому числі масивів Коціга. Методи другої і третьої групи є конструктивними і містять елементи індукції. Кожна група методів пов’язана з визначенням певного фактора або факторизації графа, який бере участь в побудові графа турніру.
Висновок. У процесі аналізу теоретичних досягнень досліджуваного напрямку виконана систематизація існуючих результатів. Всі методи побудови графів неповних турнірів розбито на три групи. Запропоновано нові підходи для їх реалізації. Це дає можливість розширити коло завдань з використанням математичних моделей на основі розмічених графів.
Завантажити повний текст в PDF (російською).
Ключові слова: справедливий неповний турнір, еквівалентний неповний турнір, гандикап турнір, дистанційна магічна розмітка, дистанційна d-антимагічна розмітка, врівноважена дистанційна d-антимагічна розмітка.
Надійшла 21.11.18
