Неполные турниры и магические типы разметок

Предложен обзор существующих теоретических результатов по вершинным магическим разметкам графов, применяемым в качестве математических моделей в задачах составления расписаний для неполных турниров. Выполнена их систематизация для адаптации к другим видам задач. Методы построения графов неполных тур...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Управляющие системы и машины
Дата:	2018
Автори:	Семенюта, М.Ф., Шерман, З.Ф., Дмитриев, О.М.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2018
Теми:	Фундаментальные и прикладные проблемы Computer Science
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/161513
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Неполные турниры и магические типы разметок / М.Ф. Семенюта, З.Ф. Шерман, О.М. Дмитриев // Управляющие системы и машины. — 2018. — № 5. — С. 13–24. — Бібліогр.: 23 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860122207723716608
author	Семенюта, М.Ф. Шерман, З.Ф. Дмитриев, О.М.
author_facet	Семенюта, М.Ф. Шерман, З.Ф. Дмитриев, О.М.
citation_txt	Неполные турниры и магические типы разметок / М.Ф. Семенюта, З.Ф. Шерман, О.М. Дмитриев // Управляющие системы и машины. — 2018. — № 5. — С. 13–24. — Бібліогр.: 23 назв. — рос.
collection	DSpace DC
container_title	Управляющие системы и машины
description	Предложен обзор существующих теоретических результатов по вершинным магическим разметкам графов, применяемым в качестве математических моделей в задачах составления расписаний для неполных турниров. Выполнена их систематизация для адаптации к другим видам задач. Методы построения графов неполных турниров разбиты на три группы. Предложены новые подходы для их реализации. Мета — систематизувати основні теоретичні відомості, що стосуються даної тематики, виділити відриті проблеми, класифікувати методи побудови графів турнірів та уніфікувати алгоритми їх опису відповідно до класифікації. Методи. Запропоновано нові алгоритми побудови графів неповних турнірів. Це дає можливість розширити коло задач з використанням математичних моделей на основі розмічених графів Purpose. The purpose of the article is to systematize the main theoretical information related to this topic, to highlight the problems that have not been solved, to classify the methods of constructing graphs of tournaments and to unify the algorithms for their description in accordance with this classification. Methods. New algorithms for constructing incomplete tournaments graphs are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs.
first_indexed	2025-12-07T17:39:52Z
format	Article
fulltext	ISSN 0130-5395, УСиМ, 2018, № 5 13 DOI: https://doi.org/10.15407/usim.2018.05.013 УДК 519.1 М.Ф. СЕМЕНЮТА, канд. физ.-мат. наук, профессор кафедры физ.-мат. дисциплин, Летная академия Национального авиационного университета, г. Кропивницкий marina_semenyuta@ukr.net З.А. ШЕРМАН, канд. физ.-мат. наук, старший преподаватель кафедры медицинской физики и информационных технологий №2, Донецкий национальный медицинский университет, sherman.zoya@gmail.com О.Н. ДМИТРИЕВ, заведующий кафедры летной эксплуатации, аэродинамики и динамики полета, Летная академия Национального авиационного университета, г. Кропивницкий Dmitronik70@i.ua НЕПОЛНЫЕ ТУРНИРЫ И МАГИЧЕСКИЕ ТИПЫ РАЗМЕТОК Предложен обзор существующих теоретических результатов по вершинным магическим разметкам графов, приме- няемым в качестве математических моделей в задачах составления расписаний для неполных турниров. Выполнена их систематизация для адаптации к другим видам задач. Методы построения графов неполных турниров разбиты на три группы. Предложены новые подходы для их реализации. Ключевые слова: справедливый неполный турнир, эквивалентный неполный турнир, гандикап турнир, дистанционная магическая разметка, дистанционная d-антимагическая разметка, уравновешенная дистанционная d-анти ма ги- чес кая разметка. Введение Составление расписаний для неполных круго- вых турниров — одно из направлений исследо- ваний, применяемых математические модели на основе размеченных графов. При большом количестве команд, участвующих в соревнова- ниях, невозможно провести полный круговой турнир за короткое время. Поэтому возника- ет необходимость в планировании неполных турниров, имитирующих сложность полного кругового турнира. Существует несколько ти- пов неполных турниров, каждый из них имеет свои характеристики. В статье рассматрива- ются методы построения справедливых, им эквивалентных и уравновешенных (ганди- кап) неполных турниров. Ре шение проб ле мы их планирования для n команд, играющих с r оппонентами, равносильно решению задачи построения соответствующей дистанционной магической или антимагической разметки r-ре гу ляр но го графа порядка n. Термин дистанционная магическая размет- ка появился в 2009 году в статье [1]. Эта же разметка была введена независимо автора- ми работы [2] в 1994 и [3] в 2003 годах и наз- вана, в первом случае Σ разметкой, а во вто- ром – 1-вершинной магической вершинной разметкой. Подробный обзор по данной те- матике можно найти в [4] и [5]. Следующая, рассматриваемая, разметка графа — это (a, d)- дистанционная антимагическая. Она впер- вые предложена в 2012 году С. Арумугамом и Н. Камачи [6]. Д. Фрончек такую разметку назвал дистанционной d-антимагической [7]. В [6] получены первые общие результаты, 14 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев в том числе условия существования (a, d)– дистанционной антимагической разметки, а также сформулированы открытые проблемы, частично решенные в [7–12]. Для уравнове- шенных (гандикап) турниров используется уравновешенная (гандикап) дистанционная антимагическая разметка. Этот термин ввела Т. Коваржова в 2016 году, наряду с ним часто встречается термин упорядоченная дистанци- онная антимагическая разметка [7]. Все рас- смотренные выше разметки относятся к маги- ческому типу вершинных разметок графов. Вопросы существования графов турниров, методы их построения отображены в рабо- тах Д. Фрончека, П. Коварж, Т. Коваржовой, А. Шепаника, В. Крайка, Б. Фрейберга. Постановка задачи Цель данной статьи — выполнить обзор суще- ствующих теоретических результатов по вер- шинным магическим разметкам графов, при- меняемым в качестве математических моделей в задачах по составлению расписаний для не- полных турниров. Для ее реализации необходимо системати- зировать основные теоретические сведения, относящиеся к данной тематике, выделить от- крытые проблемы, классифицировать методы построения графов турниров и унифицировать алгоритмы их описания согласно этой класси- фикации. Справедливый и эквивалентный неполные турниры При планировании спортивных соревнова- ний часто возникают ситуации, когда по раз- ным причинам отсутствует возможность про- ведения полного кругового турнира. В таком случае, для составления расписания органи- заторы соревнований выдвигают следующие требования: каждая команда должна играть с одинаковым числом оппонентов; слож- ность турнира для каждой команды должна имитировать сложность полного кругово- го турнира. Для реализации второго условия выполняется ранжирование n команд, на- пример, по результатам предыдущего года [7]. Команды могут оцениваться в диапазо- не от первого до n, в соответствии с заня- тыми местами. Будем отождествлять номер команды с ее рангом. Под силой i-й команды в полном круговом турнире понимают чис- ло s n (i) = n+1 – i, а в качестве общей силы оп- понентов i-й команды принимается число S n,n–1 (i) = n(n+1)/2 – s n (i) = (n+1)(n – 2)/2+i. Последовательность всех общих сил, распо- ложенных в возрастающем порядке, образу- ет арифметическую прогрессию с разностью единица. Поэтому, для имитации аналогич- ной сложности в неполном круговом турнире необходимо получить арифметическую про- грессию из общих сил оппонентов каждой команды. Если такой турнир из n команд с r раундами, где r < n – 1 возникает из кругового турнира опусканием определенных матчей, при условии, что каждая команда должна играть одинаковое количество матчей, то его обозначают FIT(n, r) и называют справедли- вым неполным турниром. В FIT(n, r) каждая ко- манда играет с r другими командами и общая сила противников, играющих с i-й коман- дой, определяется по формуле S n,r (i) = (n+1) (n – 2)/2+i – k для каждого i и фиксирован- ной постоянной k. C другой стороны, про- пущенные матчи также образуют своего рода турнир, его обозначают EIT (n, n– r – 1) и на- зывают эквивалентным неполным турниром. В EIT (n, n – r – 1) каждая команда играет n–r–1 матчей и общая сила оппонентов S* n,n–r–1 (i) у i-й команды одинакова и равна постоянной k, т. е. S* n,n–r–1 (i) = k. Очевидно FIT (n, r) суще- ствует тогда и только тогда, когда существует его дополнение EIT(n, n – r – 1). Эти турниры изучались в работах [7, 13, 14]. Математической моделью турнира может вы- ступать конечный неориентированный граф, не содержащий петель и кратных ребер. Каж- дой команде соответствует вершина графа и две вершины — смежные, если между соответ- ствующими командами состоялся матч. Так как ранг команды совпадает с ее номером, то в качестве меток вершин графа порядка n ис- ISSN 0130-5395, УСиМ, 2018, № 5 15 Неполные турниры и магические типы разметок пользуем числа от единицы до n. Нахождение EIT(n, r) эквивалентно решению задачи су- ществования дистанционной магической раз- метки для r-регулярного графа G порядка n, а FIT(n, n – r – 1) соответствует дополнение G, т.е. (n – r – 1)-регулярный граф. Планирование FIT(n, n – r – 1) означает поиск (n – r – 1)-ре гу- ляр но го графа порядка n, допускающего дис- танционную антимагическую разметку. Пусть G = (V, E) — конечный неориенти- рованный граф без кратных ребер и петель. Через f обозначим вершинную разметку графа G, а через N (u) — множество смежности вер- шины u ∈ V (G). Вес w f (u) вершины u при раз- метке f определяют как сумму меток вершин смежных с u, т. е. w f (u) = ∑ ∈ )( )( uNv vf , где каждая вершина v ∈ V(G). Определение 1 [3]. Дистанционной магической разметкой (или 1-вершинной магической вер- шинной, или сигма разметкой) графа G = (V, E) порядка n называют биекцию f : V (G) → {1, 2, ... ..., n}, для которой существует такое натураль- ное число k, что для каждой вершины u ∈ V (G) выполняется условие w f (u) = k, где k = const. Постоянная k называется магической постоян- ной разметки f. Граф, допускающий дистанци- онную магическую разметку, называют дис- танционным магическим графом. Определение 2 [7]. Дистанционной d-анти- ма ги че ской разметкой графа G = (V, E) порядка n называется биекция f : V (G) → {1, 2, ..., n}, при которой существует такой порядок вершин G, что их веса w f (u 1 ), w f (u 2 ), ..., w f (u n ) образуют арифметическую прогрессию с разностью d, где u 1 , u 2 ,…, u n ∈ V (G), d — фиксированное не- отрицательное целое число. Граф, допускаю- щий такую разметку, называют дистанционным d-антимагическим. В этом случае, порядок вершин не имеет зна- чения и не связан с их метками, полученными в результате разметки f . Когда d = 0, f являет- ся дистанционной магической разметкой, т. е. f = f, когда d = 1, f называют дистанционной ан- тимагической. Известные результаты для указанных раз- меток способствовали нахождению условий существования EIT(n, r), которые отображе- ны в теоремах 1-4, леммах 1, 2. Отметим, что в эквивалентном неполном турнире EIT(n, r) из n команд с r раундами общая сила против- ников, играющих с i-й командой, равна числу S* n,r (i) = k для каждого i. Таким образом, для r-регулярного дистанционного магического графа порядка n, представляющего EIT(n, r), имеем w f (i) = S* n,r (i) = k. Вопрос существова- ния EIT(n, r) для четного n полностью решен Д. Фрон че ком, П. Коварж, Т. Коваржовой в [13]. Случай нечетного n рассмотрен Д. Фрон че ком в [14]. Теорема 1 [13]. Пусть EIT(n, r) — эквивалент- ный неполный турнир. Тогда r — четное. Теорема 2 [13]. Для четного n эквивалент- ный неполный турнир EIT(n, r) существует тогда и только тогда, когда n ≡ r ≡ 0 (mod4) или n ≡ r + 2 (mod4). Теорема 3 [14]. Пусть q — нечетное число, r = 2sq, где q > 1, s ≥ 1 и n = tq для некоторого не- четного t, t ≥ 2s + 1. Тогда существует эквива- лентный неполный турнир EIT(n, r). Лемма 1 [14]. Пусть q — нечетное число, r = 2sq, где q > 1, s ≥ 1. Тогда для n – (2s + 1) q ≡ 0 (mod4) и n ≥ (23 +1 + 1) q + 2 существует эквивалентный неполный турнир EIT(n, r). Лемма 2 [14]. Пусть q — нечетное число, r = 2sq, где q > 1, s ≥ 1. Тогда для n – (2s + 1) q ≡ 2 (mod4) и n ≥ (23+1 + 3) q + 2 существует эквивалентный неполный турнир EIT(n, r). Теорема 4 [14]. Пусть n — нечетное число, r = 2sq с s ≥ 1 и q — нечетным. Тогда эквивалент- ный неполный турнир EIT(n, r) существует, когда r ≤ 2 (n – 2)/7. Следствие [14]. Пусть n — нечетное число, а r — такое четное число, при котором r < n и n – r – 1 ≠ 2z для любого z > 0. Тогда справедли- вый неполный турнир FIT(n, r) существует всякий раз, когда r > 5(n – 2)/7. Справедливый неполный турнир FIT(n, r) имитирует структуру полного кругового тур- нира, но он имеет существенные недостатки: команда с наивысшим рангом один имеет оп- понентов, у которых общая сила S n,r (1) – наи- меньшая; самая сильная команда имеет боль- ше шансов на победу. В эквивалентном непол- ном турнире EIT(n, r) общая сила оппонентов 16 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев каждой команды одинакова, поэтому он не сохраняет сложность полного турнира и не может считаться справедливым. Кроме того, в EIT(n, r), также как и в FIT(n, r), сильная ко- манда имеет больше шансов на победу. Чтобы командам дать одинаковые шансы на победу необходимо устранить эти недостатки. Это воз- можно в уравновешенном неполном турнире, о нем пойдет речь в следующем разделе. Уравновешенные (гандикап) турниры Уравновешенный (гандикап) неполный турнир из n команд с r раундами обозначается HIT(n, r) и представляет собой турнир, в котором каждая команда играет с r другими командами и общая сила противников, играющих с i-й командой, определяется по формуле S n,r (i) = t – i для каж- дого i и фиксированной постоянной t. Таким образом, самая сильная команда играет с самы- ми сильными оппонентами, а самая слабая — с самыми слабыми. С точки зрения дистанцион- ных магических графов это ограничение соот- ветствует нахождению гандикап графа. Определение 3 [7]. Уравновешенной (гандикап) дистанционной d-антимагической разметкой графа G = (V,E) порядка n называется такая биекция f : V (G) → {1, 2, ..., n}, для которой f (u i ) = = i и последовательность весов w f * (u 1 ), w f * (u 2 ), ... ..., w f * (u n ) всех вершин образуют возрастающую арифметическую прогрессию с разностью d, где d ≥ 0, u 1 , u 2 , ..., u n ∈ V (G). Граф G, допускаю- щий такую разметку f , называют уравнове- шенным (или гандикап) дистанционным d-анти- магическим графом или d-гандикап графом. Когда d = 1, то речь идет о гандикап дистанци- онной антимагической разметке или, коротко, гандикап разметке и, соответственно, ганди- кап графе. В гандикап графе порядка n, вес каждой вершины i равен w f (i) = f * (i) + l = i + l, где i = 1, 2, …, n. Если G — r-регулярный d-гандикап граф порядка n, тогда он соответствует d-урав но ве- шен но му (или d-ганикап) турниру из n ко- манд, сыгравших r раундов, который обозна- чим HIT (n, r, d) и HIT (n, r), если d = 1. Остановимся на случае d = 1. Исследованию этого направления посвящены работы [7, 15— 21]. На протяжении всего дальнейшего изло- жения, будем идентифицировать номер вер- шины u i гандикап графа с ее меткой i, таким образом, f (u i ) = f (i) = i. Лемма 3 [15, 19]. В r-регулярном гандикап графе порядка n вес каждой вершины i равен w(i) = (r—1)(n+1)/2+i. Лемма 3 часто используется, чтобы пока- зать, что r-регулярный гандикап граф порядка n не существует при соответствующих значе- ниях параметров r и n. Этот факт и некоторые другие свойства графов способствовали дока- зательству теоремы 6. Теорема 6 [15, 19]. Не существует 1-регулярный гандикап граф. Не существует 2-регулярный гандикап граф. Не существует r-регулярный гандикап граф порядка n, если оба r и n — четные. Не существует (n – 1)-регулярный ганди- кап граф. Не существует (n – 2t)-регулярный ганди- кап граф для любого натурального [1, / 2 ]t n∈ ⎢ ⎥⎣ ⎦ . Не существует r-регулярный гандикап граф порядка n для r ≡ 1(mod4) и n ≡ 2(mod4). Не существует (n – 3)-регулярный гандикап граф порядка n. В теоремах 7—12 поднимается вопрос суще- ствования r-регулярного гандикап графа по- рядка n для четного n и нечетного r. Теорема 7 [15, 18]. Для n ≡ 0(mod8) и r ≡ ≡ 1,3(mod4) существует r-регулярный гандикап граф порядка n для всех допустимых значений r, 3 ≤ r ≤ n – 5. Теорема 8 [18, 19]. Для n ≡ 0(mod8), n ≥ 8 и нечетного r существует r-регулярный ганди- кап граф порядка n тогда и только тогда, когда 3 ≤ r ≤ n – 5. Теорема 9 [16]. Пусть G — r-регулярный ган- дикап граф порядка n, где n ≡ 2(mod4). Тогда r ≡ 3(mod4) и r ≤ n – 7. Теорема 10 [16]. Для n ≡ 2(mod4) существует r-регулярный гандикап граф порядка n тогда и только тогда, когда 3 ≤ r ≤ n – 7 и r ≡ 3(mod4), кроме r = 3 и n ≤ 26, и возможно, когда r = n – 7 и n ∈ {14, 18, 22, 26, 34, 38}. ISSN 0130-5395, УСиМ, 2018, № 5 17 Неполные турниры и магические типы разметок Теорема 11 [19]. Для n ≡ 4(mod8), n ≥ 12 и не- четного r существует r-регулярный гандикап граф порядка n, удовлетворяющий условию 7 ≤ r ≤ n – 5. Теорема 12 [19]. Существует r-регулярный гандикап граф четного порядка n для всех n ≥ 28 и 3 ≤ r ≤ n – 11, за исключением случаев, когда оба n ≡ 2(mod4) и r ≡ 1(mod4). Далее представлены результаты для частных случаев r-ре гу ляр ных гандикап графов. Теорема 13 [17]. Пусть n ≡ 9(mod18). Тогда существует 4-регулярный гандикап граф по- рядка n. Лемма 4 [19]. Пусть G — 3-регулярный ган- ди кап граф порядка n. Тогда существует 3-ре- гу ляр ный гандикап граф порядка n+8. Лемма 5 [19]. Пусть G — 5-регулярный ган- дикап граф порядка n. Тогда существует 5-ре- гу ляр ный гандикап граф порядка n+12. Теорема 14 [16]. Для n ≡ 0(mod4) существует (n – 7)-регулярный гандикап граф порядка n каждый раз, когда n ≥ 16. Теорема 15 [16]. Для n ≡ 2(mod4) существует (n – 7)-регулярный гандикап граф порядка n, когда n = 30 или n ≥ 42. Пусть HIT(n, r, d) — r-регулярный d-ган ди- кап граф порядка n имеет d-гандикап разметку f, тогда вес каждой его вершины i равен w (i) = = d f(i) + l = di + l, где i = 1, 2, …, n, l = const. Д. Фрончек изучал HIT(n, r, 2) при n ≡ 0(mod16) и n ≡ 8(mod16), а также получил необходимые условия их существования. Теорема 16 [18]. Если существует r-ре гу- лярный 2-гандикап граф HIT(n, r, 2) четного порядка n, тогда 4 ≤ r ≤ n – 6. Теорема 17 [18]. Существует r-регулярный 2-гандикап граф HIT(16m, r, 2) порядка 16m для каждого натурального m и каждого чет но го r, удовлетворяющего условию 4m + 2 ≤ r ≤ 12m – 2. Более сильный результат получен в следую- щей теореме. Теорема 18 [18]. Существует r-регуляр-ный 2-ган дикап граф HIT(n,r,2) порядка n ≡ 0(mod16), когда 4 ≤ r ≤ n – 6. Условия существования HIT(n, 6, 2) и r-ре- гулярного 2-гандикап графа порядка n с n ≡ ≡ 8(mod16) отображены в теоремах 19, 20. Теорема 19 [18]. Существует 6-регулярный 2-гандикап граф HIT(8c, 6, 2) порядка 8c для нечетного c, c ≥ 5. Теорема 20 [18]. Существует r-регулярный 2-гандикап граф порядка n для каждого нату- рального n ≡ 8(mod16), n ≥ 56 и каждого четного r, удовлетворяющего условию 6 ≤ r ≤ n – 50. Доказательство теорем 16—20 Д. Фрончек осуществил построением соответствующих r-регулярных 2-гандикап графов с использова- нием множества магических прямоугольников определенных размеров. Б. Фрейберг в [21] обобщил описанные ре- зультаты на d-гандикап графы. Кроме того, он нашел условия существования HIT(n, r, d) для разных параметров n, r и d. Теорема 21 [21]. Если HIT(n, r, d) существу- ет, тогда: 1) w (i) = di + (r – d)(n + 1)/2, для всех i = 1, 2, …, ..., n; 2) если n — четное, тогда r ≡ d(mod2); 3) если n — нечетное, тогда r ≡ 0(mod2); 4) ( )2 1 ( 1)n d d d⎡ ⎤≥ + + +⎢ ⎥. Теорема 22 [21]. Пусть d — четное число, d ≥ 2 и G — произвольный d-регулярный дистан- ционный магический граф порядка v ≥ d + 2. Пусть n = vt для любого четного натурального t ≥ d + 2. Если d ≡ 0(mod4) или t ≡ 0(mod4), тогда существует HIT(n, 2d, d). Теорема 23 [21]. Пусть d, t, v — четные на- туральные числа, d ≥ 2, v ≥ d + 2 и n = vt. Если d ≡ 0(mod4) или v ≡ t ≡ 0(mod4), тогда существу- ет HIT(n, r, d) для всех таких четных r, что 2d ≤ r ≤ n – 2d – 2. Теорема 24 [21]. Для каждого нечетного d и для каждого такого четного r, 2d + 1 ≤ r ≤ n – – 2d – 3 существует HIT(n, r, d) при условии: n ≡ 0(mod4d + 4), n ≥ (d + 1)(d + 3) и d ≡ 1(mod4) или n ≡ 0(mod4d + 4), n ≥ (d + 1)(d + 5) и d ≡ 3(mod4), или n ≡ 2d + 2(mod4d + 4), n ≥ (d + 1)(d + 3) и d ≡ 3(mod4). После теорем 23, 24 осталось небольшое число неизвестных допустимых значений r, 18 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев для которых существует HIT(n, r, d). В связи с этим Б. Фрейберг сформулировал следующие открытые проблемы. Проблема 1 [21]. Для всех n ≡ 0(mod16), n ≥ 32 построить HIT(n, r, 3) для r ∈ {5, n – 7}. Проблема 2 [21]. Для всех n ≡ 0(mod16), n ≥ 48 построить HIT(n, r, 4) для r ∈ {6, n – 8}. Проблема 3 [21]. Для данного d ≥ 1 найти все такие значения n, для которых HIT(n, r, d) су- ществует для некоторых r. Проблема 3 частично решена для d = 1 и тех случаев d, о которых речь идет в теоремах 22—24. О методах построения графа турнира Как отмечалось, задача составления расписа- ния неполного турнира для n команд, играю- щих с r другими командами, эквивалентна за- даче построения r-регулярного графа поряд- ка n, допускающего определенный тип раз- метки. Такой граф назовем графом турнира. Далее речь пойдет о методах его построения. Начнем изложение материала с планирования полного кругового турнира с четным числом команд. Это будет полезно для понимания алгоритма действий в других рассмотренных авторами случаях. Разложением графа G на графы изоморфные H является разбиение множества ребер G на подмножества, каждое из которых порождает подграф — компоненту разложения, изоморф- ный H, и каждое ребро G принадлежит только одной компоненте разложения. Разложение графа G называют циклическим, если все его компоненты получаются из одной базовой (или нескольких базовых) действием на нее циклической подстановки вершин G. Фактором графа называют его остовный под граф, не являющийся вполне связным [22]. Если все компоненты разложения G — факто- ры, то такое разложение называют фактори- зацией. Регулярный остовный подграф степе- ни n графа G — его n-фактор. 1-Факторизация графа G представляет собой множество Ф 1-факторов G , и каждое ребро графа G при- надлежит одному и только одному фактору из Ф. О графе G говорят, что он 1-факторизуем. Полный граф K 2n 1-факторизуем [22] и 1-факторизация K 2n содержит (2n – 1)(2n – 3) разных 1-факторов. Если предположить, что в полном круговом турнире участвует четное число команд, напри- мер, 2n, где n — натуральное число, то такой турнир задается полным графом K 2n , а одному раунду соответствует 1-фактор в K 2n . Таким об- разом, для составления расписания требуется построить 1-факторизацию K 2n . К наиболее распространенным методам по- строения разложений графов относится цикли- ческий метод. Действие этого метода проде- монстрируем на примере построения 1-фак то- ри за ции графа К 2n [23]. Пусть вершинам К 2n со- ответствуют числа 1, 2, 3, …, 2n. Сгруппируем ребра в множество F i по следующему правилу: F i : (i, 2n), (i + j, i – j) для j=1, 2, 3, …, n – 1, где i = 1, 2, 3, …, n – 1. Тогда F 1 состоит из ребер (1, 2n), (1 + j, 1 – j); F 2 — из ребер (2, 2n), (2 + j, 2 – j) и так далее, где j = 1, 2, 3, …, n – 1. Все целые числа в запи- си ребер, за исключением 2n, приведены по модулю 2n – 1 для размещения в диапазоне 1, 2, 3, …, 2n – 1. Множество ребер F i является 1-фактором, так как i + j пробегает вершины i + 1, i + 2, …, ..., i + n – 1, а i – j пробегает вершины i + n, i + n + 1, i + n + 2, …, i – 1. 1-Фактор F i изобра- жен на рис. 1. Следовательно, совокупность F i для i = 1, 2, … ..., 2n – 1 представляет собой 1-факторизацию графа К 2n . Указанная 1-факторизация — мате- матическая модель расписания полного круго- вого турнира 2n команд. Разобьем все методы построения графов не- полных турниров на три группы. В ранних ра- ботах Д. Фрончека, П. Коварж, Т. Коваржовой [13, 14] методы планирования справедливых FIT(n, r) и эквивалентных EIT(n, r) неполных турниров базировались на построении допол- нений графов K a , K b , входящих в декартовое произведение или композицию, и свойствах магических прямоугольников размера a× b, ISSN 0130-5395, УСиМ, 2018, № 5 19 Неполные турниры и магические типы разметок в том числе массивов Коцига. Их включим в первую группу. Поскольку спектр допусти- мых значений параметров n и r, найденных методами первой группы, ограниченный, то для построения d-гандикап графов при d = 1 предложены конструктивные методы [19], ко- торые в этой классификации составят вторую группу, а также подход с «bubble» графом [15, 19, 20], его отнесем к третьей группе. Каждая группа методов связана с определением не- которого фактора или факторизации (раз- ложения) графа, участвующего в построении графа турнира. Методы первой группы имеют общую идею изложения и содержат незначительные моди- фикации, связанные с типом турнира. Для их понимания достаточно остановиться на кон- кретном случае неполного турнира. Напомним понятия массива Коцига и смещенного масси- ва Коцига. Под массивом Коцига KA(a, b) = (e ij ) пони- мают матрицу размера a× b, в которой каждая строка содержит каждое из чисел 1, 2, …, b, один раз и сумма элементов в каждом столбце равна одной и той же постоянной c = a(b + 1)/2. Эле- менты f ij смещенного массива Коцига LKA(a, b; l) различны, образуют множество из ab различ- ных последовательных целых чисел, с наимень- шим элементом l + 1 и f ij = e ij + l + (i – 1). Суммы элементов в столбце LKA(a, b; l) равны числу c = a (ab + 2l + 1)/2 [14]. Рассмотрим EIT(n, r), удовлетворяющий условию теоремы 3. Пусть r = 2sq, где q — не- четное число, q > 1, s ≥ 1 и n = tq для некоторого нечетного t, t ≥ 2s + 1. В построение графа тур- нира задействуем доказательство теоремы 3 [14]. Выделим три этапа и опишем детально каждый из них. Этап 1. Воспользуемся тем фактом, что для нечетного t полный граф K t имеет разложе- ние на гамильтоновы циклы. Таким образом, существует 2s-регулярный фактор F графа K t . Зададим F. Этап 2. Строим граф G = F [K q ], называемый композицией графов F и K q . Граф G = F [K q ] является (2sq)-регулярным и состоит из q изо- морфных копий фактора F. Смежность вершин разных копий определяется правилами постро- ения композиции. Обозначим через {x 1j , x 1j , … ..., x tj } — множество вершин j-й копии F. Этап 3. Строим смещенный массив Коцига LKA (q, t; 0) = (f ij ). Разметку f графа G задаем следующим образом: f (x ij ) = f ij , где i = 1, 2, , …, t, j = 1, 2, , …, q. Поскольку каждая вершина x ij является смежной с 2s вершинами одной ко- пии, то ее вес определяется по формуле w (x ij ) = = 2s—1q (qt + 1), где c = q (qt + 1)/2 — сумма эле- ментов столбца LKA(q, t; 0). Таким образом, f — дистанционная магиче- ская разметка G. Следовательно, граф G реали- зует EIT(n, r). Конструктивные методы второй группы с эле- ментами индукции детально освещены в [19]. Они — частные, также как и подход с «bub ble» графом, так как применяются для построения определенных типов гандикап графов. i–3 i–2 i–1 i 2n i+1 i+2 i–3 Рис. 1. 1-Фактор F i графа K 2n Рис. 2. Граф F 2 ∪ F 3 20 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев Пусть n ≡ 0(mod8), r ≡ 1,3(mod4) и 3 ≤ r ≤ n – 5. Опишем построение r-регулярного гандикап графа G порядка n, опираясь на результаты ра- бот [15, 20], в которых искомый граф получен введением некоторой «bubble» структуры. В данной статье мы отказались от этой громозд- кой конструкции и предлагаем новый подход. Под расстоянием между двумя вершинами i и j размеченного графа порядка n будем по- нимать число ρ (i, j) = min (\|i – j \|, n – \|i – j \|). Так как r — нечетное число, не меньшее трех, то в качестве искомого графа G — рассмотрим та- кой r-регулярный граф, у которого r = 2s + 3 и его (2s + 3)-факторизация состоит из одного 1-фактора F 1 с ребрами, окрашенными в крас- ный цвет, двух 1-факторов F 2 , F 3 — с синими ребрами и 2s 1-факторов F 4 , F 5 , …, F 2s+3 с чер- ными ребрами. Процесс построения реализу- ем в три шага. Ш а г 1. Строим F 1 : (1, 4k + 1), (2, 4k + 2), (3, 4k + 3), …, (4k, 8k), где ρ 1 (i, j) = 4k для каж- дого ребра (i, j) графа F 1 . Обозначим w r (i) — вес вершины в факторе F 1 . Таким образом, w r (i) = 4k + i для i ∈ {1, 2, …, 4k} и w r (i) = –4k + i для i ∈ {4k + 1, 4k + 2, …, 8k}. Ш а г 2. Строим 1-факторы: F 2 : (1, 2), (3, 4), …, (2k – 1, 2k), (2k + 1, 2k + 2), … ..., (8k – 3, 8k – 2), (8k – 1, 8k), где ρ 2 (i, j) = 1 для каждого ребра (i, j) графа F 2 ; F 3 : (1, 4k – 1), (2, 4k), …, (2k – 1, 2k + 1), (2k, 2k + + 2), …, (4k + 1, 8k – 1), (4k + 2, 8k), …, (6k – 1, 6k + 1), (6k, 6k + 2), где р 3 (i, j)∈{2, 6, …, 4k – 6, 4k – 2} для ребер (i, j) графа F 3 . Найдем дизъюнктивное объединение фак- торов F 2 и F 3 . Граф F 2 ∪ F 3 состоит из 4k ком- понент H i , где i = 1, 2, …,4k, каждая из которых изоморфна полному двудольному графу K 2,2 (рис. 2). Ш а г 3. Необходимо увеличить степень r графа, полученного после 2-го шага, с учетом условий: r ≤ n – 5 и r ≡ 1,3(mod4). Строим фак- торы F 4 , F 5 , …, F 2s+3 с черными ребрами так, чтобы граф ∪ 32 4 + = s i iF был дистанционным маги- ческим. Тогда искомый граф ∪ 32 1 + = = s i iFG будет гандикап графом степени большей, чем три. Разобьем множество вершин G на пары [1, 8k], [2, 8k – 1], …, [4k, 4k + 1] при этом сум- ма меток вершин каждой пары равна 8k + 1. Данные пары вершин не должны быть смеж- ными в G и вершины каждой пары – концы двух смежных ребер, которые войдут в разные 1-факторы. Увеличим степень каждой верши- ны графа F 1 ∪ F 2 ∪ F 3 на два, добавлением ре- бер. Для этого зададим два 1-фактора F 4 и F 5 с черными ребрами, используя указанное выше разбиение вершин. Чтобы избежать повторе- ний красных и синих ребер, в F 4 включим ре- бра, соединяющие вершины, расположенные на расстоянии два. Тогда F 4 имеет вид: (1, 3), (2, 4), …, (8k – 3, 8k – 1), (8k – 2, 8k). Фактор F 5 строим так, чтобы сохранить вес 8k+1 для вер- шин графа F 4 ∪ F 5 . Зададим F 5 следующим об- разом: (1, 8k – 2), (3, 8k), (2, 8k – 3), (4, 8k – 1),… (4k – 2, 4k + 1), (4k, 4k + 3), где ρ 5 (i, j) ∈ {3, 5, …, 8k – 5, 8k – 3} для ребер (i, j) графа F 3 . Следовательно, граф ∪ 5 1=i iF является 5-ре- гу лярным гандикап графом. Веса его вершин определяются по формуле w (i) = 16k + 2 + i для i ∈ {1, 2, …, 8k}. Повторяя действия, описанные в 3-м шаге, продолжаем увеличивать степень r графа ∪ 5 1=i iF пока не получим гандикап граф ∪ 32 1 + = = s i iFG с r ≤ ≤ n – 5 и r ≡ 1,3(mod4). Заключение В процессе анализа теоретических достижений исследуемого направления выполнена систе- матизация существующих результатов. Все ме- тоды построения графов неполных турниров разбиты на три группы. Предложены новые подходы для их реализации. Это дает возмож- ность расширить круг задач с использованием математических моделей на основе размечен- ных графов. ISSN 0130-5395, УСиМ, 2018, № 5 21 Неполные турниры и магические типы разметок СПИСОК ЛИТЕРАТУРЫ 1. Sugeng K.A., Froncek D., Miller M., Ryan J., Walker J. On distance magic labeling of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 2009. Vol. 71. P. 39—48. 2. Vilfred V. Sigma labelled graphs and circulant graphs. Ph.D. Thesis, University of Kerala, India, March 1994. 3. Miller M., Rodger C., Simanjuntak R. Distance magic labelings of graphs. Australasian Journal of Combinatorics. 2003. Vol. 28. P. 305—315. 4. Arumugam S., Froncek D., Kamatchi N. Distance magic graphs — a survey. Journal of the Indonesian Mathematical Society. Special Edition. 2011. P. 11—26. 5. Gallian J. A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. 2017. DS6: Dec 22. 432 p. 6. Arumugam S., Kamatchi N. On (a; d)-distance antimagic graphs. Australasian journal of combinatorics. 2012. Vol. 54. P. 279—287. 7. Froncek D. Handicap distance antimagic graphs and incomplete tournaments. AKCE International Journal of Graphs and Combinatorics. 2013. Vol. 10, N2. P. 119—127. 8. Kamatchi N., Ramalakshmi A., Nilavarasi S, Arumugam S. A note on distance magic and distance antimagic graphs. Electronic Notes in Discrete Mathematics. 2015. Vol. 48. P. 183—187. 9. Nalliah M. Antimagic labelings of graphs and digraphs: Ph. D. thesis. M. Nalliah. The National Centre for Advanced Research in Discrete Mathematics, University of Kalasalingam, 2014. 21 р. 10. Семенюта М.Ф. Про дистанційну антимагічну розмітку графів. Збірник наукових праць НАУ інститут кібернетики ім. В.М. Глушкова «Теорія оптимальних рішень». 2016. С. 26—32. 11. Семенюта М.Ф. (a, d)-дистанційна антимагічна розмітка окремих типів графів. Міжнародний науково- теоретичний журнал інституту кібернетики ім. В.М. Глушкова НАУ України «Кібернетика і системний аналіз». 2016. Т. 52, №6.С. 135—142. 12. Семенюта М.Ф. Про (a, d)-дистанційну антимагічну та 1-вершинну бімагічну вершинну розмітки певних типів графів. Міжнародний науково-теоретичний журнал інституту кібернетики ім. В.М. Глушкова НАУ України «Кібернетика і системний аналіз». 2018. Т. 54, №2.С. 134—141. 13. Froncek D., Kovar P., Kovarova T. Fair incomplete tournaments. Bull. Inst. Combin. Appl. 2006. Vol. 48. P. 31—33. 14. Froncek D. Fair incomplete tournaments with odd number of teams and large number of games. Congr. Numer. 2007. Vol. 187. P. 83—89. 15. Shepanik A. Graph labelings and tournament scheduling. MS Thesis. University of Minnesota Duluth. 2015. 55 p. 16. Froncek D., Shepanik A. Regular handicap tournaments of high degree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2016. Vol. 3, N3. P. 159—164. 17. Kovar P., Kravcenko M., Krbecek M., Silber A. Handicap labelings of 4-regular graphs. Discrete mathematics. 2017. Vol. 15, N2. P. 331—335. 18. Froncek D. A note on incomplete regular tournaments with handicap two of order n ≡ 0(mod8). Opuscula Math. 2017. Vol. 37, N4. P. 57—556. 19. Froncek D., Kovar P., Kovarova T., Krajc B., Kravcenko M., Shepanik A., Silber A. On regular handicap graphs of oven order. Electronic Notes in Discrete Mathematics. 2017. Vol. 60. P. 69—76. 20. Froncek D., Shepanik A. Regular handicap graph of order n ≡ 0(mod8). Electronic Journal of Graph Theory and Applications. 2018. Vol. 6, N2. P. 208—218. 21. Freyberg B. Distance magic type and distance anti-magic-type labelings of Graphs. Ph.D.Thesis. Michigan Technological University, Michigan, USA. 2017. 150 p. 22. Харари Ф. Теория графов. М.: Мир, 1973. 300 с. 23. Семенюта М. Ф. Дослідження розкладів та нумерацій графів: Дис. ... канд. фіз.-мат. наук.: 01.01.08. К., 2008. 190 с. Поступила 21.11.2018 22 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев REFERENCE 1. Sugeng K.A., Froncek D., Miller M., Ryan J., Walker J. On distance magic labeling of graphs, Journal of Combinatorial Mathematics and Combinatorial Computing. 2009. Vol. 71. P. 39—48. 2. Vilfred V. Sigma labelled graphs and circulant graphs. Ph.D. Thesis, University of Kerala, India, March 1994. 3. Miller M., Rodger C., Simanjuntak R. Distance magic labelings of graphs. Australasian Journal of Combinatorics. 2003. Vol. 28. P. 305—315. 4. Arumugam S., Froncek D., Kamatchi N. Distance magic graphs — a survey. Journal of the Indonesian Mathematical Society. Special Edition. 2011. P. 11—26. 5. Gallian J. A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. 2017. DS6: Dec 22. 432 p. 6. Arumugam S., Kamatchi N. On (a; d)-distance antimagic graphs Australasian journal of combinatorics. 2012. Vol. 7. Froncek D. Handicap distance antimagic graphs and incomplete tournaments. AKCE International Journal of Graphs and Combinatorics. 2013. Vol. 10, N2. P. 119—127. 8. Kamatchi N., Ramalakshmi A., Nilavarasi S, Arumugam S. A note on distance magic and distance antimagic graphs. Electronic Notes in Discrete Mathematics. 2015. Vol. 48. P. 183—187. 9. Nalliah M. Antimagic labelings of graphs and digraphs: Ph. D. thesis. The National Centre for Advanced Research in Discrete Mathematics, University of Kalasalingam, 2014, 21 р. 10. Semeniuta М. On distance antimagic labeling of graphs. Collection of Scientific Works of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine «The Theory of Optimal Solutions». 2016. P. 26—32. (in Ukrainian). 11. Semeniuta М. (a, d)-distance antimagic labeling of certain types of graphs. International theoretical science journal of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine «Cybernetics and Systems Analysis». 2016. Vol. 52, №6. P. 135—142. (in Ukrainian). 12. Semeniuta М. On (a, d)-distance antimagic and 1-vertex bimagic vertex labeling of certain types of graphs. International theoretical science journal of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine «Cybernetics and Systems Analysis». 2018. Vol. 54, №2. P. 134—141. (in Ukrainian). 13. Froncek D., Kovar P., Kovarova T. Fair incomplete tournaments. Bull. Inst. Combin. Appl. 2006. Vol. 48. P. 31—33. 14. Froncek D. Fair incomplete tournaments with odd number of teams and large number of games. Congr. Numer. 2007. Vol. 187. P. 83—89. 15. Shepanik A. Graph labelings and tournament scheduling. MS Thesis. University of Minnesota Duluth. 2015. 55 p. 16. Froncek D., Shepanik A. Regular handicap tournaments of high degree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2016. Vol. 3, N3. P. 159—164. 17. Kovar P., Kravcenko M., Krbecek M., Silber A. Handicap labelings of 4-regular graphs. Discrete mathematics. 2017. Vol. 15, N2. P. 331—335. 18. Froncek D. A note on incomplete regular tournaments with handicap two of order n ≡ 0(mod8). Opuscula Math. 2017. Vol. 37, N4. P. 57—556. 19. Froncek D., Kovar P., Kovarova T., Krajc B., Kravcenko M., Shepanik A., Silber A. On regular handicap graphs of oven order. Electronic Notes in Discrete Mathematics. 2017. Vol. 60. P. 69—76. 20. Froncek D., Shepanik A. Regular handicap graph of order n ≡ 0(mod8). Electronic Journal of Graph Theory and Applications. 2018. Vol. 6, N2. P. 208—218. 21. Freyberg B. Distance magic type and distance anti-magic-type labelings of Graphs. Ph.D.Thesis. Michigan Technological University, Michigan, USA. 2017. 150 p. 22. Harari F. Graph Theory. M.: Peace, 1973. — 300 p. (in Russian). 23. Semeniuta М. Investigation of timetables and numbering graphs: candidate thesis of physical and mathematical sciences: 01.01.08. К., 2008. 190 p. (in Ukrainian). Received 21.11.2018 ISSN 0130-5395, УСиМ, 2018, № 5 23 Неполные турниры и магические типы разметок М.Ф. Семенюта, канд. фіз.-мат. наук, професор кафедри фізико-математичних дисциплін, Льотна академія Національного авіаційного університету, м. Кропивницький marina_semenyuta@ukr.net З.А. Шерман, канд. фіз.-мат. наук, викладач кафедри медичної фізики та інформаційних технологій №2, Донецький національний медичний університет, sherman.zoya@gmail.com О.М. Дмітрієв, завідувач кафедри льотної експлуатації, аеродинаміки та динаміки польоту, Льотна академія Національного авіаційного університету, м. Кропивницький Dmitronik70@i.ua НЕПОВНІ ТУРНІРИ І МАГІЧНІ ТИПИ РОЗМІТОК Вступ. В спортивному світі існють різні види турнірів, планування яких базується на побудові графових моделей. Кожен вид турніру має свої характеристики. В даній статті розглянуто справедливі, еквівалентні їм та врівно- важені неповні турніри. Створення турнірної сітки для n команд, що грають з r опонентами для таких турнірів, рівно розв’язанню задачі побудови відповідної дистанційної магічної або антимагічної розмітки r-регулярного графа порядку n. Мета — систематизувати основні теоретичні відомості, що стосуються даної тематики, виділити відриті пробле- ми, класифікувати методи побудови графів турнірів та уніфікувати алгоритми їх опису відповідно до класифікації. Методи. Запропоновано нові алгоритми побудови графів неповних турнірів. Це дає можливість розширити коло задач з використанням математичних моделей на основі розмічених графів. Результат. Всі методи побудови графів турнірів розбиті на три групи. До методів першої групи віднесені ті, які базуються на властивостях магічних прямокутників, в тому числі масивів Коціга. Методи другої і третьої груп є конструктивними і містять елементи індукції. Кожна група методів пов’язана з визначенням певного фактора або факторизації графа, який бере участь в побудові графа турніру. Висновок. У процесі аналізу теоретичних досягнень досліджуваного напрямку виконана систематизація отри- маних результатів. Запропоновано нові підходи для їх реалізації, що дає можливість розширити коло завдань з використанням математичних моделей на основі розмічених графів. Ключові слова: справедливий неповний турнір, еквівалентний неповний турнір, гандикап турнір, дистанційна магічна розмітка, дистанційна d-антимагічна розмітка, врівноважена дистанційна d-антимагічна розмітка. Marina Semeniuta, PhD in Phys.-Math. Sciences, associate professor, Department of Physics and Mathematics Sciences of the Flight Academy of the National Aviation University, st. Dobrovolsky, 1, Kropivnitsky, 25005, Ukraine, marina_semenyuta@ukr.net Zoya Sherman, PhD in Phys.-Math. Sciences, senior lecturer, Department of Medical physics and information technology №2 of Donetsk National Medical University, st. Pryvokzalnaya, 27, Liman, 84404, Donetsk region, Ukraine, sherman.zoya@gmail.com Oleh Dmitriiev, PhD, head of the department of flight operations, aerodynamics and flight dynamics of the Flight Academy of the National Aviation University, st. Dobrovolsky, 1, Kropivnitsky, 25005, Ukraine, Dmitronik70@i.ua INCOMPLETE TOURNAMENTS AND MAGIC TYPES OF LABELING Introduction. There is a variety of types of sports tournaments whose planning is based on the construction of graph models. Each type of tournament has its own characteristics. In this paper, fair, equitable and balanced partial competitions are con- 24 ISSN 0130-5395, Control systems and computers, 2018, № 5 М.Ф. Семенюта, З.А. Шерман, О.Н. Дмитриев sidered. Creating a tournament grid for n teams playing with r opponents for such tournaments is equivalent to solving the problem of constructing an appropriate distant magic or antimagic labeling of the r-regular graph of order n. Purpose. The purpose of the article is to systematize the main theoretical information related to this topic, to highlight the problems that have not been solved, to classify the methods of constructing graphs of tournaments and to unify the algo- rithms for their description in accordance with this classification. Methods. New algorithms for constructing incomplete tournaments graphs are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs. Results. All methods of constructing graphs of tournaments are divided into three groups. The methods of the first group included those based on the properties of magic rectangles, including Kotsih arrays. Methods of the second and third groups are constructive and contain elements of induction. Each group is related to the definition of a particular factor or factoriza- tion of the graph, which is involved in building a graph of the tournament. Conclusion. In the process of analyzing the theoretical advances of the studied problem the systematization of the exist- ing results has been made. All methods for constructing incomplete tournament graphs are divided into three groups. New approaches for their realization are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs. Keywords: fair incomplete tournament, equalized incomplete tournament, handicap tournament, distance magic labeling, d-antimagic distance labeling, d-handicap distance antimagic labeling.
id	nasplib_isofts_kiev_ua-123456789-161513
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0130-5395
language	Russian
last_indexed	2025-12-07T17:39:52Z
publishDate	2018
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format	dspace
spelling	Семенюта, М.Ф. Шерман, З.Ф. Дмитриев, О.М. 2019-12-12T21:12:46Z 2019-12-12T21:12:46Z 2018 Неполные турниры и магические типы разметок / М.Ф. Семенюта, З.Ф. Шерман, О.М. Дмитриев // Управляющие системы и машины. — 2018. — № 5. — С. 13–24. — Бібліогр.: 23 назв. — рос. 0130-5395 DOI: https://doi.org/10.15407/usim.2018.05.013 https://nasplib.isofts.kiev.ua/handle/123456789/161513 519.1 Предложен обзор существующих теоретических результатов по вершинным магическим разметкам графов, применяемым в качестве математических моделей в задачах составления расписаний для неполных турниров. Выполнена их систематизация для адаптации к другим видам задач. Методы построения графов неполных турниров разбиты на три группы. Предложены новые подходы для их реализации. Мета — систематизувати основні теоретичні відомості, що стосуються даної тематики, виділити відриті проблеми, класифікувати методи побудови графів турнірів та уніфікувати алгоритми їх опису відповідно до класифікації. Методи. Запропоновано нові алгоритми побудови графів неповних турнірів. Це дає можливість розширити коло задач з використанням математичних моделей на основі розмічених графів Purpose. The purpose of the article is to systematize the main theoretical information related to this topic, to highlight the problems that have not been solved, to classify the methods of constructing graphs of tournaments and to unify the algorithms for their description in accordance with this classification. Methods. New algorithms for constructing incomplete tournaments graphs are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы Computer Science Неполные турниры и магические типы разметок Неповні турніри і магічні типи розміток Incomplete Tournaments and Magic Types of Labeling Article published earlier
spellingShingle	Неполные турниры и магические типы разметок Семенюта, М.Ф. Шерман, З.Ф. Дмитриев, О.М. Фундаментальные и прикладные проблемы Computer Science
title	Неполные турниры и магические типы разметок
title_alt	Неповні турніри і магічні типи розміток Incomplete Tournaments and Magic Types of Labeling
title_full	Неполные турниры и магические типы разметок
title_fullStr	Неполные турниры и магические типы разметок
title_full_unstemmed	Неполные турниры и магические типы разметок
title_short	Неполные турниры и магические типы разметок
title_sort	неполные турниры и магические типы разметок
topic	Фундаментальные и прикладные проблемы Computer Science
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	https://nasplib.isofts.kiev.ua/handle/123456789/161513
work_keys_str_mv	AT semenûtamf nepolnyeturniryimagičeskietipyrazmetok AT šermanzf nepolnyeturniryimagičeskietipyrazmetok AT dmitrievom nepolnyeturniryimagičeskietipyrazmetok AT semenûtamf nepovníturníriímagíčnítipirozmítok AT šermanzf nepovníturníriímagíčnítipirozmítok AT dmitrievom nepovníturníriímagíčnítipirozmítok AT semenûtamf incompletetournamentsandmagictypesoflabeling AT šermanzf incompletetournamentsandmagictypesoflabeling AT dmitrievom incompletetournamentsandmagictypesoflabeling

Неполные турниры и магические типы разметок

Репозитарії

Схожі ресурси