Российская академия наук

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ

ИНСТИТУТ МАТЕМАТИКИ ИМ. С.Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РАН

(ИМ СО РАН)

УДК 519.17, 519.72

№ госрегистрации 01201172121

Инв. №

УТВЕРЖДАЮ

Директор член-корреспондент РАН _ Гончаров С.С.

«_» 2012 г.

ОТЧЕТ

О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ

В рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы по государственному контракту № 14.740.11. шифр заявки 2010-1.5-502-001- по теме:

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

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

Наименование этапа № 4: «Анализ полученных результатов»

(итоговый) Руководитель НИР, д.ф.-м.н. _ А.В. Косточка Новосибирск

СПИСОК ИСПОЛНИТЕЛЕЙ

Косточка А.В. (Введение, Заклюрук. темы, в.н.с. ИМ СО РАН, чение, Приложения А–Г, разделы д.ф.-м.н _ 1.1, 2, 3, 4) отв. исполнитель темы, зав. лаб. Бородин О.В. (Реферат, ПрилоИМ СО РАН, д.ф-м.н. жения А–Г, разделы 1.7, 2, 4) _ гл.н.с. ИМ СО РАН, д.ф.-м.н. Кельманов А.В. (разделы 1.6, 2) _ в.н.с. ИМ СО РАН, д.ф.-м.н. Пяткин А.В. (разделы 1.1, 1.6) _ в.н.с. ИМ СО РАН, д.ф.-м.н. Кротов Д.С. (разделы 1.3, 1.4) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Глебов А.Н. (разделы 1.1, 1.2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Добрынин А.А. (разделы 1.2, 2,4) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Мельников Л.С. (раздел 1.2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Потапов В. Н. (разделы 1.3, 1.4) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Августинович С.В. (раздел 1.3) _ Токарева Н.Н. (разделы 1.5, 2) с.н.с. ИМ СО РАН, к.ф.-м.н. _ с.н.с. ИМ СО РАН, к.ф.-м.н.

Фрид А.Э. (раздел 1.4) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Могильных И.Ю. (разделы 1.4, 2) _ аспирант ИМ СО РАН Замбалаева Д.Ж. (раздел 1.2) _ аспирант ИМ СО РАН Воробьев К.В. (раздел 1.3) _ аспирант НГУ Коломеец Н.А. (раздел 1.4) Отчет 64 с., 70 источников, 4 прил.

Тема: ФУНДАМЕНТАЛЬНЫЕ ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ В ПРОБЛЕМАХ

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

Ключевые слова: теория графов; раскраска графов; декомпозиция графов; инварианты графов; совершенные раскраски; булевы функции; теория кодирования; бент-функции;

криптография; дистанционно регулярные коды; кластерный анализ.

Основным объектом исследования являются актуальные проблемы в области применения теоретико-графовых моделей и методов дискретной математики к проблемам анализа коммуникационных сетей, надежности и эффективности передачи информации, защиты информации и анализа данных.

Выполнение НИР в целом направлено на проведение поисковых фундаментальных исследований в области современной математики (теория графов и ее приложения, методы эффективного кодирования и передачи информации, защита информации, анализ данных и распознавание образов) с целью получения научных результатов мирового уровня, на подготовку и закрепление в сфере науки и образования научных и научно-педагогических кадров, а также формирование эффективных и жизнеспособных научных коллективов.

В результате выполнения НИР исполнителями получен ряд результатов мирового уровня. Получены новые фундаментальные результаты, найдены новые подходы, разработаны новые алгоритмы, опубликованы новые статьи, защищены диссертации, осуществляется внедрение результатов в учебный процесс НГУ.

В ходе выполнения этапа 4 проведён анализ полученных в рамках НИР результатов. К основным результатам отнесены следующие:

Показано, что каждый плоский субкубический плоский граф, т.е. граф со степенями не более 3, обхвата не менее 12 допускает 2-дистанционную 5-раскраску.

Доказана предписанная ациклическая 4-раскрашиваемость плоских графов, не содержащих ни 3-циклов, смежных с циклами длины не более 6, ни 4-циклов, смежных с циклами длины не более 7.

Доказано, что любой планарный граф, в котором 3-циклы находятся на расстоянии не менее 4 друг от друга и не имеют общих ребер с 5-циклами, является 3-раскрашиваемым.

Получено исчерпывающее описание строения плоских графов в терминах звезд при младших вершинах. Опровергнута гипотеза Йендроля и Харанта.

Доказана справедливость гипотезы Вудала–Сеймура о наличии миноров полного двудольного графа Ks,t в (s + t)-хроматических графах для широкого диапазона параметра t для каждого фиксированного значения s.

Асимптотически (и в некоторых случаях точно) найдено хроматическое число для графов, тесно связанных с раскрасками евклидовых пространств.

Рассмотрена задача о двух коммивояжерах в различных постановках. Для задачи на максимум построен приближенный алгоритм c оценкой точности 7/9 и кубической временной сложностью.

Показана NP-полнота задачи о наименее плотном разрезе и предложены полиномиальные алгоритмы её решения для некоторых классов графов, в частности, для графов пересечений единичных интервалов и графов с ограниченной древесной шириной.

Установлен критерий, который по параметрам совершенной 2-раскраски двоичного куба определяет, является ли она кратным совершенным кодом заданного радиуса некоторой кратности. Показано, что существуют кратные совершенные коды любого нечетного радиуса сколь угодно большой длины.

В терминах совершенных структур охарактеризованы коды с параметрами трижды укороченных 1-совершенных двоичных кодов. Доказано, что соответствующие расширенные коды всегда порождают совершенную раскраску вершин гиперкуба в шесть цветов.

Доказано, что существует экспоненциальное число неэквивалентных пропелинейных расширенных совершенных кодов. Показано, что все такие коды имеют малый ранг, который на единицу больше ранга расширенного линейного кода Хэмминга.

Получено описание всех бент-функций от 2k переменных, находящихся на минимальном расстоянии от квадратичной бент-функции.

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

Доказана NP-полнота актуальных задач разбиения конечного множества векторов, а также выбора подмножеств векторов в евклидовом пространства по критерию минимума суммы квадратов расстояний.

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

ИМ СО РАН – Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук.

НГУ – Новосибирский государственный университет ММФ – Механико-математический факультет Анализ и обобщение полученных результатов Раскраска графов и смежные вопросы Оптимизационные задачи на графах и сетях Совершенные раскраски и коды Экстремальные структуры и построение кодов Булевы функции с экстремальными свойствами (бент-функции) Сложностные вопросы анализа данных и распознавания образов Разработка программы внедрения результатов ПНИР в образовательный 1. Подготовка итогового отчета по НИР Показатели Заключение Список использованных источников Приложение В. Список сделанных исполнителями докладов Приложение Г. Программа научных семинаров по 4 этапу проекта Выполнение поисковых научно-исследовательских работ по проекту направлено на проведение фундаментальных исследований в области анализа теоретико-графовых моделей в проблемах анализа структурных объектов, теории кодирования, передачи информации и криптографии, обработке данных. Основной целью НИР проекта является получение научных результатов мирового уровня, позволяющих укрепить позиции российской школы в области теоретических направлений в дискретной математике и информатике (методы эффективного кодирования и передачи информации, защита информации, анализ данных и распознавание образов, анализ структур методами теории графов). Одной из целей проведения работ является привлечение научных сотрудников, студентов и аспирантов к современным передовым методам и подходам в научно-исследовательской работе в указанных областях, что будет способствовать повышению эффективности и устойчивости российских научных коллективов.

Запланированная работа по этапу 4 включала анализ и обобщение полученных результатов в области анализа структуры граф-моделей передачи информации и обработки данных, в теории кодирования информации, в теории и приложений бент-функций в криптографии и в смежных областях.

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

На этапе 4 разработана программа внедрения результатов выполненных поисковых научно-исследовательских работ в образовательный процесс. Результаты НИР включены в состав читаемых в НГУ общих и специальных математических курсов «Теория графов», «Совершенные структуры», «Теория графов и алгоритмы», «Теория кодирования», «Криптография и криптоанализ», «Коды и схемы», «Экстремальные задачи анализа данных и распознавания образов», используются при проведении специальных семинаров по современным разделам математики в Институте математики им. С.Л. Соболева СО РАН.

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

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

В итоговом отчете проведен анализ и обсуждаются возможные обобщения и применение полученных результатов, в том числе полученные на последнем этапе.

1.1. Раскраска графов и смежные вопросы Структура многих информационных и вычислительных систем естественно моделируются графами и их обобщениями (гиперграфами). Современное развитие информационнотелекоммуникационных технологий приводит к появлению новых постановок задач в области теории и методов раскраски графов.

1. В теоретических исследованиях проблемы распределения радиочастот в сетях связи используется следующая теоретико-графовая модель. Вершины плоского графа (источники) должны быть раскрашены (получить частоты) так, чтобы цвета (целые числа) любых двух вершин, находящихся друг от друга на расстоянии 1, отличались не менее чем на p, а вершин на расстоянии 2 – не менее чем на q. Таким образом, нахождение (p,q)-дистанционного хроматического числа позволяет минимизировать количество занятых частот [1-4]. При p = 1 и q = 2 возникает задача 2-дистанционной раскраски плоских графов. Под обхватом графа понимается длина наименьшего цикла. Получен новый результат по 2-дистанционным раскраскам. Показано, что каждый плоский субкубический плоский граф (т.е. граф со степенями не более 3) обхвата не менее 12 допускает 2-дистанционную 5-раскраску.

Тем самым улучшены результаты Распо, Монтасьера, у которых обхват графов был не менее 14 [5] и результаты Аве с обхватом графов не менее 13 [6]. Эти результаты находятся на мировом уровне и опубликованы в ведущем зарубежном журнале по дискретной математике.

2. Бородин и др. (2002) высказали гипотезу, что каждый плоский граф предписанно ациклически 5-раскрашиваем и доказали, что 7 цветов достаточно. В пяти зарубежных работах она подтверждена для следующих классов плоских графов: без 3- и 4-циклов, без 4- и 5циклов, без 4- и 6-циклов, без 4-циклов и хордальных 6-циклов, без 4-циклов и 3-циклов на расстоянии менее 3 друг от друга, а также без 4-циклов и пересекающихся 3-циклов. Также доказано, что плоские графы без 4-циклов предписанно ациклически 6-раскрашиваемы. Доказано, что каждый плоский граф без 4-циклов предписанно ациклически 5-раскрашиваем, что является совместным усилением шести зарубежных работ в этом направлении.

Этот результат является выдающимся, далеко опережающим мировой уровень в области ациклической раскраски плоских графов. В 2011 г. он был включен в число важнейших результатов ИМ СО РАН.

3. Граф G является (j,k)-раскрашиваемым, если можно так разбить его вершины на два множества V1 и V2, что в подграфе G[V1] степень каждой вершины не превышает j, а в G[V2] степень каждой вершины не превышает k. Доказано, что при k 2j+2 каждый граф с наибольшей средней степенью не более 2(2–(k+2)/(j+2)(k+1)) является (j,k)-раскрашиваемым. С другой стороны, построены графы с наибольшей средней степенью сколько угодно близкой к 2(2–(k+2)/(j+2)(k+1)), которые не являются (j,k)-раскрашиваемыми.

На самом деле доказан еще более точный результат: найдено наилучшее достаточное условие для (j,k)-раскрашиваемости графа G в терминах минимума, величины = (2–(k+2)/(j+2)(k+1))|W| – |E(G[W])| по всем подмножествам W множества V(G).

j,k(W,G) Конкретно, доказано, что каждый граф G с > –1/(k+1) является (j,k)-раскрашиваемым.

С другой стороны, построено бесконечно много не (j,k)-раскрашиваемых графов G с j,k(G) 4. В развитие предыдущего результата, доказано, что каждый граф с наибольшей средней степенью не более 14/5 является (1,1)-раскрашиваемым. С другой стороны, построены графы с наибольшей средней степенью сколько угодно близкой к 14/5, которые не являются (1,1)-раскрашиваемыми. Это, в частности, улучшает результат Хавета и Серени. Отметим, что результат отличается от того, который получился бы подстановкой j=k=1 в предыдущий результат.

5. Гипотеза Хадвигера утверждает, что любой граф с хроматическим числом k содержит минор полного k-вершинного графа Kk. Эта гипотеза доказана только для k 6. Неизвестно даже, существует ли (хотя бы маленькое) число c > 0 такое, что любой граф с хроматическим числом k содержит минор полного ck-вершинного графа Kck. Близкая к ней гипотеза утверждает, что любой n-вершинный граф с числом независимости содержит минор полного (n/)-вершинного графа Kn/. Фокс доказал, что любой n-вершинный граф с числом независимости содержит минор полного (n/(2–c))-вершинного графа K(n/(2–c)), где c > 1/57. Нами доказан более сильный результат с c > 1/19.2.

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

6. Гиперграф называется d-вырожденным, если каждый его непустой подграф имеет вершину степени (в этом подграфе) не более d. Каждый d-вырожденный гиперграф легко покрасить в d+1 цвет. Гиперграф G является почти d-вырожденным, если сам G не является dвырожденным, но каждый его собственный подграф является d-вырожденным. В частности, если G является почти d-вырожденным, то после удаления любого ребра получившийся гиперграф является (d+1)-раскрашиваемым. Изучены и охарактеризованы почти dвырожденные гиперграфы, которые нельзя раскрасить в d+1 цвет. По определению каждый такой гиперграф является (d+1)-критическим по раскраске.

Эта задача является NP-полной, т.е. не существует хорошего описания всех kкритических графов. Результаты дают описание интересного подкласса таких графов: графов, после удаления любого ребра которых есть очевидный способ раскраски в k – 1 цвет.

Работа является шагом к пониманию структуры k-критических графов и решает задачи, поставленные Бородиным в 1974 г. (проблема 1.4. в книге [7]).

7. Пусть G – гиперграф с раскрашенными ребрами. Тогда радужным подграфом в G называется подграф, все ребра которого раскрашены разными цветами. Цветовой степенью вершины v в графе с раскрашенными ребрами называется число разных цветов, используемых на ребрах, инцидентных с v. Ванг и Ли выдвинули гипотезу, что при k 4 каждый граф с раскрашенными ребрами и минимальной цветовой степенью k содержит радужное паросочетание с как минимум k/2 ребрами. Правильно раскрашенный K4 не имеет такого паросочетания, в связи с чем возникло ограничение k 4 в гипотезе. Ли и Ксу доказали, что гипотеза справедлива для некоторых других правильно раскрашенных полных графов. Позже Ле Солнер, Стокер, Венгер и Вест доказали гипотезу для четных k. В настоящем проекте гипотеза доказана полностью.

Разноцветные паросочетания графах тесно связаны с паросочетаниями в 3униформных 3-дольных гиперграфах. Известно, что нахождение наибольшего паросочетания в таких гиперграфах является NP-трудной задачей. Таким образом, оценки на размеры паросочетаний, особенно когда доказательство дает полиномиальный алгоритм построения «больших» паросочетаний, интересны для теории и методов оптимизации. Доказательства представленных результатов обладают этим свойством.

8. Получена точная верхняя оценка 2D – 1 для реберного 2-дистанционного хроматического числа плоских графов с достаточно большим обхватом, где D – максимальная степень графа.

Результат не улучшаем, и является одним из немногих точных результатов по так называемой сильной реберной раскраске, исследуемой уже более 20 лет.

9. Доказана предписанная ациклическая 4-раскрашиваемость плоских графов, не содержащих ни 3-циклов, смежных с циклами длины не более 6, ни 4-циклов, смежных с циклами длины не более 7 (все известные ранее достаточные условия ациклической 4раскрашиваемости полностью запрещали 4-циклы).

Этот результат усиливает целый ряд зарубежных результатов и является первым по предписанной ациклической 4-раскраске, когда 4-циклы допускаются, хотя на них и налагаются некоторые необходимые ограничения.

10. Харант и Йендроль дали описание строения плоских графов в терминах звезд при младших вершинах, поглощающее ряд известных результатов в этой области. Там же была сформулирована гипотеза об идеальном описании такого рода. Ранее Бородиным и Ивановой были построены два класса контрпримеров к данной гипотезе. Сейчас получено описание конструкции, в котором все параметры являются неулучшаемыми Данный результат усиливает известный зарубежный результат, доводя его до неулучшаемого и поглощая при этом ряд более ранних результатов. Попутно даются два класса контрпримеров к известной гипотезе Харанта-Йендроля.

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

Полученный результат закрывает некое направление в структурной теории плоских графов. Перечисленные приближенные результаты входят в недавний обзор С.Йендроля, готовящийся к публикации в журнале Discrete Mathematics. Полученный результат превосходит мировой уровень.

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

Дальнейшие направления исследований: полученные результаты и развитая техника позволяют надеяться на полное решение проблемы о дефективных 2-раскрасках графов с данной максимальной средней степенью. Другими словами, развитие наших методов может позволить для каждых j и k найти точное значение функции f((j,k) – наибольшего m такого, что любой граф с максимальной средней степенью менее m имеет (j,k)-раскраску: разбиение множества вершин графа G на два подмножества V1 и V2 таких, что максимальная степень в порожденном подграфе G[V1] не превосходит j, а максимальная степень в порожденном подграфе G[V2] не превосходит k.

13. Доказано обобщение известной теоремы Гретцша о 3-раскрашиваемости плоских графов: если к плоскому графу без циклов длины 3 добавить вершину степени не больше 4, то полученный граф по-прежнему 3-раскрашиваем. Результат является неулучшаемым, т.к.

если к 5-циклу добавить вершину степени 5, то 3-раскрашиваемости нет. Попутно усилен результат работы [12], в которой допускается добавление вершины степени не больше 3.

Проблема 3-раскрашиваемости плоских графов привлекает большое внимание специалистов по теории графов во всем мире. Каждый новый, тем более точный, результат в этом направлении является ценным.

14. Подготовлена большая обзорная статья о раскраске плоских графов [13], принятая в печать в международный журнал Discrete Mathematics.

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

15. Исследована задача подсчёта правильных рёберных 3-раскрасок, тотальных 4раскрасок, а также L(2,1)-нумераций спана 5 для кубических графов. Получены экспоненциальные верхние и нижние оценки для числа таких раскрасок в n-вершинном кубическом графе. Также предложены алгоритмы динамического программирования для подсчёта числа указанных раскрасок в графах с ограниченной древесной шириной.

16. Доказана 4-раскрашиваемость графов без индуцированных подграфов K3 и 2P3.

Ранее было известно лишь о 5-раскрашиваемости таких графов.

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

17. Доказано, что любой планарный граф, в котором 3-циклы находятся на расстоянии не менее 4 друг от друга и не имеют общих ребер с 5-циклами, является 3-раскрашиваемым.

Одним из самых известных результатов о раскрасках плоских графов является теорема Грётцша о 3-раскрашиваемости плоских графов без 3-циклов. В поисках усилений данного результата Хавел (1970) задал вопрос о том, существует ли такая константа H, что любой плоский граф с минимальным расстоянием между 3-циклами не меньше H, является 3раскрашиваемым. Из результатов Аксенова и Мельникова следует, что H > 3. Недавно гипотеза Хавела была доказана Дворжаком, Кралем и Томасом для очень больших значений H. В то же время, остаётся открытым вопрос о справедливости гипотезы Хавела для минимального возможного значения H = 4. Полученный результат является важным продвижением на пути к решению гипотезы Хавела в указанной сильной постановке, отличаясь от неё лишь требованием отсутствия общих ребер у 5-циклов с 3-циклами. Этот результат усиливает теорему Грёцша и находится на переднем краю мировых исследований в области раскрасок планарных графов.

18. Гармонической раскраской графа G называется такая правильная раскраска вершин G, в которой каждая пара цветов появляется не более чем на одной паре смежных вершин. Гармоническое хроматическое число графа G, обозначаемое h(G), равно наименьшему числу цветов, достаточному для гармонической раскраски графа G. Вычисление гармонического хроматического числа является NP-трудной задачей даже для деревьев. Доказано, что если T является лесом с n вершинами и максимальной степенью (T) (n+2)/3, то выполняется следующее равенство:

Из доказательства извлекается алгоритм полиномиальной сложности для оптимальной гармонической раскраски таких лесов и деревьев.

Дальнейшие направления исследований: построение оптимальных гармонических раскрасок для более широких классов деревьев и лесов, анализ гармонических раскрасок ребер графов. Гармонические раскраски графов k цветов – это гомоморфизмы этих графов в полный k-дольный граф. Проблема исследования структуры гомоморфизмов является одной из важнейших в математике.

19. Пусть K*s,t обозначает граф, полученный из полного двудольного графа Ks,t путем добавления всех возможных ребер между s вершинами степени t. Мы развиваем подход из нашей ранней работы [14] для доказательства того, что если выполняется соотношение t / log2 t 1000s, то каждый граф G со средней степенью вершин t + 8s log2 s или более, имеет K*s,t-минор. Это улучшает соответствующий результат, доказанный ранее Кюном и Остасом.

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

20. Пытаясь решить гипотезу Хадвигера, Вудал и Сеймур сформулировали более слабую гипотезу, состоящую в том, что для любых s t любой граф с хроматическим числом s + t содержит минор полного двудольного графа Ks,t. Ранее Косточкой было доказано, что для любых фиксированных s и t > max{415s2 + s,(240s log2 s)8s log2 s + 1}, каждый граф с хроматическим числом s + t имеет K*s,t-минор. Это подтвердило гипотезу Вудала – Сеймура в случае, когда величина t сильно превышает значение s. Мы доказываем, что гипотеза верна и для меньших значений t, а именно, для t > C(s log2 s)3.

Дальнейшее направление исследований состоит в решении гипотезы для более широкого круга значений параметров s и t. Решение проблемы для всех значений параметров означало бы приближенное решение гипотезы Хадвигера.

21. В теории раскраски представляет интерес получение оценок на хроматическое число евклидова пространства (Rn), которое по определению есть наименьшее число цветов необходимое для раскраски всех точек в Rn так, что любые две точки на расстоянии 1 получают разные цвета. Ларман и Роджерс ввели и изучали последовательность графов Gn в Rn такую, что (Rn) (Gn) (1+o(1))n2/6. На протяжении многих лет эта оценка была наилучшей для некоторых пространств низкой размерности. Было выдвинуто предположение, что хроматическое число графов Gn больше, чем эта оценка. Мы доказали, что (Gn) также получили точную оценку в случаях n = 2k и n = 2k – 1.

Задачи раскраски евклидовых пространств изучаются около 50-ти лет. Удалось асимптотически (и в некоторых случаях точно) найти хроматическое число для графов, тесно связанных с раскрасками евклидовых пространств. Эта задача связывает теорию графов с геометрией евклидовых пространств.

22. Круговым графом называется граф пересечений конечного множества хорд в круге. Наилучшая известная верхняя оценка хроматического числа кругового графа с размером наибольшей клики k равна 50 2k. Мы получили лучшую оценку 2k–1 для более простого подкласса круговых графов, так называемых чистых графов. Используя этот результат, доказано, что хроматическое число любого кругового графа с размером наибольшей клики 3, не превосходит 38.

Задача раскраски круговых NP-трудна. Поэтому интересны полиномиальные процедуры раскраски таких графов в гарантированное число цветов. Оба результата носят такой характер. Дальнейшие исследования: обобщение разработанных методов для получения лучших общих оценок на хроматическое число круговых графов с данным размером наибольшей клики. В настоящее время известны только экспоненциальные оценки. Задача является важным частным случаем общей проблемы оптимальной раскраски графов.

23. Доказано, что любой n-вершинный гиперграф без r-регулярных подграфов имеет не более 2n–1 + r –2 ребер. Мы предполагаем, что если n > r, то любой n-вершинный гиперграф без r-регулярных подграфов, имеющий наибольшее число ребер, содержит полную звезду, т.е. 2n–1 различных ребер, содержащих какую-то вершину. Эта гипотеза доказана для n 425. При этом условие n > r ослабить нельзя.

В 1980-х годах В.А. Ташкинов получил важные результаты о r-регулярных подграфах в d-регулярных графах [15, 16]. Ситуация с регулярными подграфами гиперграфов является гораздо более трудной. В работе изучена структура наиболее плотных «плохих» примеров гиперграфов без r-регулярных подгиперграфов. Дальнейшие исследования: изучение «плохих» униформных гиперграфов без r-регулярных подгиперграфов. Если униформный гиперграф имеет много ребер, то более вероятно, что он содержит r-регулярных подграф.

24. Радужный подграф графа с раскрашенными ребрами это подграф, все ребра которого имеют разные цвета. Цветная степень вершины v есть число разных цветов, использованных на ребрах, инцидентных v. Доказано, что если n велико (а именно, n 4.25k2), то каждый n-вершинный граф G с минимальной цветной степенью k содержит радужное паросочетание с не менее чем k ребрами.

25. Числом независимости, (H), гиперграфа H называется наибольший размер подмножества вершин, не содержащего ни одного ребра H. Доказано, что если Hn есть nвершинный (r + 1)-униформный гиперграф, в котором каждое r-элементное подмножество вершин содержится в не более чем d ребрах и 0< d< n / (log n)3r2, то выполняется неравенство где cr > 0 удовлетворяет cr r/e, когда r. Значения cr улучшают и обобщают некоторые ранее известные результаты, которые используют известную теорему Атья, Комлоса, Принса, Спенсера и Семереди. Наше более короткое доказательство использует метод Ширера и Алона. Полученная нами оценка близка к наилучшей в том смысле, что для каждого r 2 и всех значений d N, существует бесконечно много гиперграфов Hn таких, что где br > 0 зависит только от r. Кроме того, для многих значений d показано, что br cr, когда. Поэтому результат почти точен для r. Также указано приложение результатов к чисr лам Рамсея для гиперграфов, связанных с независимыми окрестностями.

Проблема нахождения наибольшего независимого множества в графах и гиперграфах является одной из классических. Новое, более простое, доказательство дает лучшее понимание структуры униформных гиперграфов с ограниченным числом независимости. Дальнейшие исследования: обобщение результатов двух направлениях –для гиперграфов без других разреженных циклов и для гиперграфов без данных полных подграфов. Интересны и проблемы типа задачи Турана: сколь много ребер может иметь r-униформный гиперграф, не содержащий разреженного цикла длины 1? Задачи о существовании больших независимых множеств связаны не только с комбинаторными проблемами, но и с известными проблемами в других частях математики: теории чисел, геометрии, теории вероятностей.

26. Известный результат в теории Рамсея говорит, что порядок роста чисел Рамсея R(3,t) для графов есть t2/ log t. Рассмотрен аналог этой проблемы для униформных гиперграфов. Треугольником называется гиперграф, состоящий из ребер e, f и g таких, что |e f| = ное число n такое, что при любой раскраске ребер полного r-униформного гиперграфа Krn в два цвета, или существует треугольник первого цвета, или есть Krt второго цвета. Мы находим с точностью до логарифмического множителя порядок роста величины R(3,Krt) для всех нижнюю оценку до c1t3/2(log t)-3/4. Оказалось, что при переходе от r = 2 к r = 3 происходит скачок, а потом ситуация не меняется. Получены также оценки на некоторые другие числа Рамсея для гиперграфов.

Оценка числа независимости для графов без «разреженных» 3-циклов это результат в том же направлении, что и предыдущий. Он может также рассматриваться как оценка числа Рамсея для разреженного треугольника против полного подграфа.

27. Пусть плоский граф G G(S) образован суперпозицией множества S простых замкнутых кривых на плоскости в общем положении, т.е. кривые не имеют самопересечений, не касаются друг друга, и никакие три кривые не имеют общей точки. Вершины графа G соответствуют точкам пересечения кривых из S, а ребра — дугам кривых, соединяющим соседние точки пересечения. Построенные таким образом 4–регулярные плоские графы называются графами Грцша–Закса. Вероятно, Г. Грцш в 50-х годах прошлого столетия был первым, кто исследовал задачу раскраски графов, образованных пересечениями кривых на плоскости [17-21]. Если все кривые являются окружностями, то соответствующие графы называются графами Кёстера. Ранее в работах участников проекта были опровергнуты некоторые гипотезы о хроматическом числе таких графов, построены новые 4хроматические и 4-критические графы Грёцша-Закса [22-25]. Трудной проблемой в этой области является построение 4-хроматических и 4-критических графов Кёстера. Построен новый 4хроматический граф Кёстера на 32 вершинах, образованный пересечением 7 кривых на плоскости.

Этот граф является вершинно 4-критическим (т.е. удаление любой вершины уменьшает хроматическое число графа), но не реберно 4-критическим (четыре ребра являются не критическими). Дальнейшее направление исследований состоит в построении 4-критических графов Кестера и новых графо Гретцша-Закса.

28. Коради и Хайнал доказали в 1962 г. гипотезу Эрдеша о том, что любой граф с минимальной степенью не менее 2k и n 3k вершинами содержит k вершинно непересекающихся циклов. Эта оценка точна, т.к. для каждого k есть бесконечное множество экстремальных примеров. Важным случаем является n = 3k, т.к. все неперекающиеся k циклов должны быть 3-циклами. Доказано, что при k 3 граф G с минимальной степенью не менее 2k – 1 и n 3k вершинами не содержит k вершинно неперекающихся циклов тогда и только тогда, когда либо G содержит независимое множество размера n – 2k + 1, либо k нечетно, n = 3k и G является дополнением графа, который есть объединение полного графа Kk с полным двудольным графом Kk,k.

Это является усилением классической теоремы, доказанной около 50-ти лет назад.

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

29. Одна из центральных задач раскраски графов – выяснение структуры критических по раскраске графов. В 1957 г. Дирак поставил проблему: сколь мало ребер может иметь kкритический граф? Важные результаты по этой проблеме были получены Галлаи (1963), Оре (1967), Кривелевичем (1999), Косточкой и Штибицем (2000-2004). Оре сформулировал гипотезу о том, какой должен быть ответ. Но все результаты были далеки от этой гипотезы даже для наиболее простого случая k = 4. Проблема не раз была включена в списки важных проблем по раскраске графов. В рамках проекта Косточка с соавторами получили асимптотическое решение этой проблемы. Проблема полностью решена для k = 4 и любого n, а также для каждого k и n 1 (mod k – 1). Для этих значений k и n подтверждена справедливость гипотезы Оре. Интересные приложения этих результатов к раскраске графов получены Бородиным и другими. В частности, получено простое доказательство теоремы Гретцша о 3-раскрашиваемости плоского графа без треугольников. Дальнейшее направление исследований состоит в полном доказательстве гипотезы Оре и описании экстремальных графов, решении аналогичных проблем для гиперграфов и для предписанной раскраски.

1.2. Оптимизационные задачи на графах и сетях Рассматривается несимметричная задача о двух коммивояжерах на максимум, заключающаяся в нахождении двух реберно непересекающихся ориентированных гамильтоновых циклов максимального веса в полном ориентированном графе. Данная задача является обобщением классической задачи коммивояжера на максимум, а также модификацией симметричного случая задачи о двух коммивояжерах на максимум, который активно исследуется в последнее время. Известно, что задача коммивояжера и все содержательные варианты задачи о двух коммивояжерах NP-полны. Поэтому представляет интерес вопрос о выделении полиномиально разрешимых подклассов этих задач и о построении эффективных приближенных алгоритмов их решения с гарантированными оценками точности [26-38].

1. Для задачи о двух коммивояжерах на минимум различными весовыми функциями ребер, принимающими значения 1 и 2 (задача 2-PSP(1,2)-min-2w) построены следующие приближенные алгоритмы: a) алгоритм c оценкой точности 7/5 (без учета аддитивной константы) и кубической временной сложностью. б) алгоритм c оценкой точности 4/3 (без учета аддитивной константы) и временной сложностью O(n5).

В последнее время наряду с классической задачей коммивояжёра некоторыми авторами рассматривается такое естественное её обобщение, как задача об m коммивояжёрах (mPSP), состоящая в поиске m рёберно непересекающихся гамильтоновых циклов минимального или максимального суммарного веса в полном взвешенном графе. Из результатов Де Корта следует, что задача m-PSP NP-трудна [29, 30]. Наибольший интерес у исследователей вызывает задача о двух коммивояжёрах (2-PSP). Нами построены два полиномиальных алгоритма с гарантированными оценками точности для специального случая задачи 2-PSP на минимум, когда веса рёбер графа принимают значения 1 и 2, причём весовые функции различны для двух гамильтоновых циклов. Оба алгоритма значительно улучшают ранее полученную для данной задачи оценку точности 11/7. В основе алгоритмов лежит специальная теоретико-графская техника последовательного «улучшения» двух рёберно непересекающихся частичных туров в полном графе и метод перераспределения весовых вкладов между вершинами графа, типичный для исследования плоских графов, и ранее использованный Берманом и Карпински при построении приближённого алгоритма для задачи одного коммивояжера на минимум с весами рёбер 1 и 2.

2. Для задачи о двух коммивояжерах на максимум (задача 2-PSP-max) построен приближенный алгоритм c оценкой точности 7/9 и кубической временной сложностью. Для случая, когда весовая функция принимает значения в промежутке [1,q], получена модификация указанного алгоритма, имеющая оценку точности (7q + 3)/(9q + 1).

Полученный результат обеспечивает наилучшую на сегодняшний день оценку точности 7/9 эффективного алгоритма для наиболее общего варианта задачи о двух коммивояжёрах на максимум с произвольными неотрицательными весами рёбер. Указанная оценка точности превосходит как ранее полученную для этой же задачи Агеевым, Бабуриным и Гимади оценку 3/4, так и наилучшую на данный момент оценку 25/33 для «более простой» задачи одного коммивояжёра на максимум [37], что говорит о высоком качестве полученного результата и его соответствии передовому уровню мировых исследований в области задач маршрутизации. При разработке алгоритма использована оригинальная техника раскрасок рёбер графа, позволяющая построить пару гамильтоновых циклов нужного веса.

3. Для несимметричной задачи о двух коммивояжерах на максимум построен алгоритм, имеющий асимптотическую оценку точности 2/3 и кубическую оценку временной сложности.

Применительно к несимметричной задаче о двух коммивояжёрах на максимум, повторена (с точностью до асимптотики) оценка точности 2/3 эффективного приближенного алгоритма, ранее полученная в работе Каплана и др. для несимметричной задачи одного коммивояжёра. Как и в случае с разработанным нами алгоритмом с оценкой 7/9 для симметричной задачи 2-PSP-max, данный алгоритм основан на построении специальной раскраски ребер вспомогательного орграфа и последующем выделении пары рёберно непересекающихся частичных туров достаточно большого веса.

4. Доказано, что любой планарный граф с обхватом не менее 6 является (5,5)разбиваемым. Иными словами, множество вершин такого графа можно разбить на два подмножества так, что в подграфе, порожденном каждым подмножеством, число вершин любой цепи не превосходит 5.

Михоком в середине 80-х годов прошлого века было введено понятие путевой (a,b)разбиваемости графов, которое с тех пор активно исследуется. Им же было показано, что для любых фиксированных значений параметров a, b существуют плоские графы, не являющиеся (a,b)-разбиваемыми. При этом во всех известных примерах таких графов содержится большое число циклов длины 3. Поэтому вызывает интерес вопрос о том, для какого наименьшего значения g > 3 существуют такие константы a, b, что любой плоский граф с обхватом не менее g является (a,b)-разбиваемым. Из полученного нами результата следует, что искомое значение g не превосходит 6.

5. Показана NP-полнота задачи о наименее плотном разрезе и предложены полиномиальные алгоритмы её решения для некоторых классов графов, в частности, для графов пересечений единичных интервалов и для графов с ограниченной древесной шириной.

Плотностью разреза в графе называется отношение числа имеющихся рёбер разреза к их максимально возможному количеству (которое равно произведению мощностей долей разреза). Этот параметр является важной характеристикой уязвимости сетей с точки зрения разрушения линий связи (ребер графа). Задача о наименее плотном разрезе заключается в поиске в данном графе разреза с минимальной плотностью, что соответствует «узкому месту» сети, т.е. набору линий связи, разрушение которых приведет к наибольшему ухудшению работы сети.

6. Показано, что задача определения жёсткости графов без индуцированного подграфа 2K2 является NP-полной.

Жесткостью графа называется минимальное отношение мощности разрезающего множества графа к числу компонент связности, получающихся после его удаления. Этот параметр является важной характеристикой уязвимости сетей с точки зрения разрушения узлов связи (вершин графа). Также показано, что жёсткость 25 в таких графах влечёт их гамильтоновость, т. е. для них выполняется гипотеза Хватала. Поскольку гипотеза Хватала в общем случае остается недоказанной (и неопровергнутой) уже более 35 лет, то результат имеет мировой уровень.

7. Пусть связная коммуникационная сеть имеет гексагональную структуру, вложимую в правильную гексагональную решетку на плоскости. Функционирование сети оценивается суммой расстояний между всеми узлами сети в естественной метрике (индекс Винера W или дистанция графа [39-45]). Пусть происходит разрушение сети так, что оставшаяся сеть все еще сохраняет гексагональную структуру. После последовательности разрушающих воздействий образуются изолированные друг от друга гексагональные подсети одинакового размера, не связанные друг с другом. В этом случае оценочная характеристика сети будет определяться как сумма индексов Винера этих подсетей. Описана структура подсетей (в классе гексагональных цепей), для которых сумма их индексов Винера зависит только от их количества и размера. Именно, доказано, что W ( ) (h ), где есть множество подсеW (G ) тей, суммирование ведется по всем подсетям G, а (h) есть полином третьей степени от числа колец h в подсетях (размер подсетей). Разработанный подход может быть использован для характеризации свойств гексагональных сетей.

1.3. Совершенные раскраски и коды 1. Под совершенной раскраской в m цветов (совершенной m-раскраской) графа G с матрицей A понимается раскраска множества вершин графа G в множество цветов 1,..,m такая, что число вершин цвета j, смежных с фиксированной вершиной цвета i, не зависит от выбора последней вершины и равно aij. Матрица A называется матрицей параметров совершенной раскраски. Основной задачей является поиск новых совершенных раскрасок различных графов, особый интерес представляют совершенные 2-раскраски графов Джонсона. Отметим, что полностью регулярные, в том числе совершенные коды могут быть определены как совершенные раскраски. Полностью регулярные коды обладают хорошими алгеброкомбинаторными свойствами и включают в себя многие известные коды, такие как, совершенные, расширенные совершенные, Препараты, некоторые БЧХ и другие [46-57].

Дистанционно-бирегулярным графом G называется двудольный граф, каждая вершина которого является полностью регулярными кодом; массивы пересечений двух вершин совпадают, если эти вершины принадлежат одной доле. Соединив вершины, находящиеся на расстоянии 2 в G, получим два графа, именуемых половинными графами дистанционнобирегулярного графа G. Известно, что половинные графы дистанционно-бирегулярного графа являются дистанционно-регулярными. Примером дистанционно-бирегулярного графа является граф, индуцированный совокупностью вершин графа Хэмминга H(n,2), имеющих вес d и d+1. Половинными графами такого графа являются графы Джонсона J(n,d) и J(n,d+1).

Совершенную 2-раскраску половинного графа G’ дистанционно-бирегулярного графа G назовем сбалансированной, если вершины второго половинного графа G’ имеют ровно 2 различных цветовых состава окрестностей в графе G.

Полученные в этом направлении результаты:

1.1. Показана связь совершенных раскрасок половинных графов дистанционнобирегу-лярных графов и существование новых совершенных 2-раскрасок графов Джонсона J(n,w).

1.2. Доказано, что раскраска вершин графа G’, при которой вершины одного цветового состава красятся в один цвет, является совершенной раскраской в 2 цвета, найдены параметры раскраски. На основе вышеописанных результатов получена новая серия совершенных 2-раскрасок графов Джонсона J(n,4) и J(n,5) из систем троек и четверок Штейнера.

2. Среди транзитивных кодов можно особо выделить прополинейные коды, как коды, наиболее близкие к групповым, так как они позволяют определить групповую операцию на кодовых словах. Код называется прополинейным, если существует набор подстановок px, где x из C, что (i) Для любого x выполняется: px+px(C)=C (ii) Для любых кодовых слов x и y выполняется: px+px(y)=px py. Нетрудно видеть, что свойство (i) эквивалентно транзитивности кода C. Используя теоретико-групповую терминологию, свойство (ii) можно переформулировать следующим образом: группа автоморфизмов кода С содержит регулярную подгруппу, действующую транзитивно на всех его кодовых словах. Последнее свойство позволяет определить бинарную операцию на кодовых словах кода С: x*y=x+px(y), относительно которой код C образует группу. Очевидно, что группа, задаваемая операцией *, зависит от выбора подстановок px. Такую группу называют прополинейной структурой на коде С. Отметим, что для одного кода может существовать большое количество как различных, так и неизоморфных прополинейных структур на нем. Это говорит о потенциальной возможности использования прополинейных кодов на практике в криптографии - в аналогах таких криптосистем, как криптосистемы Мак-Элиса и Ниддерайтера. Отдельно среди прополинейных структур на коде можно выделить нормализованно-прополинейные, для которых px=py тогда и только тогда когда x+y принадлежат ядру кода С. Коды с такими прополинейными структурами называются нормализованно-прополинейными. Поиск прополинейных структур является предпочтительным с вычислительной точки зрения и, возможно, с практической, для применения в асимметричных криптосистемах. Среди основных проблем и задач, связанных с прополинейными кодами можно выделить нахождение новых прополинейных кодов и получение прополинейного нетранзитивного кода.

В это направлении получены следующий результат:

Найдены новые бесконечные серии нормализованно-прополинейных совершенных кодов из транзитивных кодов классификации Малюгина кодов, получаемых из кода Хэмминга одношаговыми свитчингами. Также доказано, что код Беста с параметрами (10,40,4) является транзитивным кодом, который не является прополинейным.

3. Пусть Hn – это гиперкуб размерности n. Вершины куба – двоичные наборы длины n;

вершины смежны, если соответствующие им наборы отличаются ровно в одной координате.

Весом wt(y) вершины y Hn называется количество единиц в этом наборе. Расстояние Хэмминга d(x,y) между вершинами x,y Hn – это количество позиций, в которых x и y различны.

. Отображение является совершенной раскраской вершин куба в k цветов с матрицей параметров если оно сюрьективно и для каждых i, j у любой вершины цвета i число соседей цвета j равно. Соответственно раскраска вершин куба в 2 цвета называется совершенной с матрицей параметab ров, если каждая вершина первого цвета имеет a соседей первого цвета и b соседей второго цвета, а каждая вершина второго цвета имеет c соседей первого цвета и d соседей второго. Подмножество вершин графа называется k-кратным совершенным кодом радиуса r, если для каждой вершины шар радиуса r с центром в этой вершине содержит в точности k кодовых вершин. В случае k = 1 мы получаем классическое определение совершенного кода.

Задача перечисления всех параметров n, r, k при которых такие коды существуют, была решена независимо Зиновьевым, Леонтьевым и Тиетвайненом. При произвольном k эта проблема еще далека от решения. В соответствии с введенными определениями ставится задача:

найти все n, b, c такие, что соответствующая совершенная раскраска будет совершенным kкодом. Полученные результаты по совершенным раскраскам:

3.1. Установлен критерий, который по параметрам совершенной 2-раскраски двоичного n-куба определяет, является ли она кратным совершенным кодом заданного радиуса r > некоторой кратности. Показано, что существуют кратные совершенные коды любого нечетного радиуса сколь угодно большой длины.

3.2. В терминах совершенных структур охарактеризованы коды с параметрами трижды укороченных 1-совершенных двоичных кодов. Доказано, что соответствующие расширенные коды (с расстоянием 4) всегда порождают совершенную раскраску (регулярное разбиение) вершин гиперкуба в шесть цветов.

3.3. Совершенная раскраска с параметрами является кратным совершенным кодом радиуса r тогда и только тогда, когда Pr ( 1, n 1) = 0, при этом кратность кода k = При r = 1 критерий выглядит так: c = a + 1, т. е. параметрами совершенных раскрасок, являющихся совершенными кратными кодами, будут с кратностью k = c. Известно, что такие совершенные раскраски существуют для любых допустимых b, c, причем они будут кратными совершенными кодами любого нечётного радиуса, так как по определению, n 1) = 0 при нечётных r. Таким образом, m, l, r N : r 1 (mod 2) существуют кратные совершенные коды радиуса 1 при n = 2m l+1 кратности k = i · l для всех i {1,..., 2m}, i 1 (mod 2). Эти же коды будут кратными совершенными кодами любого нечётного радиуса. Рассмотрены критерии также для случаев r = 2 и r = 3. Приведены все совершенные раскраски, являющиеся кратными совершенными кодами радиуса 2 в 10-мерном кубе и соответствующие им кратности.

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

4. Коды с параметрами несколько раз укороченных двоичных 1-совершенных кодов имеют параметры, близкие к параметрам совершенных кодов. В частности, трижды (и меньшее число раз) укороченные 1-совершенные коды являются оптимальными. До настоящего времени о множестве всех кодов с такими параметрами больше ничего известно не было.

Нами получены следующие результаты.

Установлены регулярные свойства всех таких кодов (варианты дистанционной инвариантности, полной регулярности, корреляционная иммунность характеристической функции). Это дало возможность классифицировать эти кодов длины 12 при помощи ЭВМ, число классов эквивалентности равно 237610. Аналогичный результат получен для дважды укороченных 1-совершенных кодов. Вычислена группа автоморфизмов Z2Z4-линейных 1совершенных двоичных кодов.

5. Пусть G = (V, E) – регулярный граф. Для всякого кода (т.е. подмножества вершин) С определим дистанционное разбиение множества вершин этого графа относительно C: V = i=0,..., рCi, где р = max{d(x, C): x C} является радиусом покрытия кода C. Код C в G называется полностью регулярным, если любая вершина из слоя Cj имеет j, j, j соседей соответственно из слоев Сj1, Cj и Cj+1. Набор чисел {j, j, j : j = 0,..., р} называется массивом пересечения кода C. Вершинами графа Джонсона J(n, w) являются все w-элементные подмножества n-элементного множества; две вершины смежны, если их пересечение имеет мощность w 1. Совокупность w-элементных подмножеств n-элементного множества (блоков), называется t (n, w, )-схемой, если любое t- элементное подмножество содержится в точности в блоках. Рассматриваются лишь схемы, у которых все блоки различны. Блоки такой схемы можно рассматривать как вершины графа Джонсона. Силой схемы называется максимальное t, для которого она является t (n, w, )-схемой.

Известно, что полностью регулярные коды в графах Джонсона можно рассматривать как подкласс t-схем со специальными комбинаторными свойствами. Ранее разными авторами было получено конструктивное описание всех полностью регулярных кодов силы 0 в графах Джонсона, а также показано, что всякая блок-схема силы w – 1 с размером блока w является полностью регулярным кодом в графе J(n, w). Эти схемы включают в себя широко известные системы троек и четверок Штейнера. Здесь рассматриваются классические конструкции Оллтопа расширения блок-схем из существующих и показывается, что их применение к полностью регулярным кодам дает новые полностью регулярные коды. В качестве исходных блоксхем для этих конструкций берутся блок-схемы с размером блока, равным половине от числа точек. Пусть D является t (n, w, )-схемой. Введем следующие обозначения: D1 = { (n + 1) : D}, D2 = {{1, …, n} \ : D}. Рассмотрим случай, когда n = 2w. Опишем две конструкции Оллтопа. Ниже обозначает подмножество вершин графа J(2w + 1, w), дополнительное к D. Получены следующие результаты:

Теорема 1. Пусть D является t (2w + 1, w, )-схемой, t четно. Тогда D1D2 является (t + 1) (2w + 2, w + 1, )-схемой.

Тогда D1 Вариант этих утверждений для полностью регулярных кодов имеет вид:

Теорема 3. Пусть С является полностью регулярным кодом с р = 1 в J(2w + 1, w). Тогда код С1 С2 является полностью регулярным в J(2w + 2, w + 1).

Теорема 4. Пусть С является полностью регулярным кодом с р = 1 в J(2w + 1, w), |С| = С использованием двух утверждений и классификации полностью регулярных кодов в J(9, 4) с радиусом покрытия 1, построены полностью регулярные коды в графе J(10, 5) с массивами пересечений {0 = 13, 0 = 12, 1 = 16, 1 = 9} и {0 = 5, 0 = 20, 1 = 8, 1 = 17}. Отметим, что конструкции расширения полностью регулярных кодов применимы к кодам произвольной силы t (в отличие от варианта конструкций для блок-схем).

6. В теории пропелинейных расширенных совершенных кодов получены результаты:

6.1. Доказано, что существует экспоненциальное число неэквивалентных пропелинейных расширенных совершенных кодов с ростом длины кодов. Показано, что все такие коды имеют малый ранг, который на единицу больше ранга расширенного линейного кода Хэмминга.

6.2. Исследованы структурные свойства пропелинейных кодов, в частности, пропелинейных совершенных двоичных кодов. Исследуется связь транзитивных кодов с пропелинейными, в частности, показано, что существует двоичный код - известный код Беста длины 10, мощности 40, с кодовым расстоянием 4, который транзитивен, но не является пропелинейным. Предложено несколько конструкций пропелинейных кодов, и новый богатый класс пропелинейных совершенных двоичных кодов, названных нормализованными. Приведена нижняя оценка числа неэквивалентных пропелинейных совершенных двоичных кодов, имеющих разные ранги.

7. Изучены свойства двоичных кодов, близких по параметрам к 1-совершенным. Произвольный двоичный (n = 2m-3, 2n-m-1, 4) -код, то есть код с параметрами трижды укороченного расширенного кода Хэмминга, является элементом регулярного разбиения (цветом совершенной раскраски) вершин n-куба на шесть частей (цветов). Произвольный двоичный (n= n = 2m-4, 2n-m, 3) -код, то есть код с параметрами трижды укороченного кода Хэмминга является элементом регулярного семейства (не обязательно разбиения) из шести подмножеств вершин n-куба. Как следствие, коды C и D являются полностью полурегулярными, то есть весовое распределение такого кода зависит только от минимального и максимального веса кодовых слов и параметров кода. Более того, если код D самокомплиментарный (антиподальный), то он полностью регулярен.

7.1. Установлено, что код с параметрами дважды или трижды укороченного кода Хэмминга порождает совершенную структуру с определёнными параметрами над булевым гиперкубом. Доказан критерий регулярности разбиения вершин графов для достаточно общего класса графов.

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

1.4. Экстремальные структуры и построение кодов 1. Множество A с заданной на нём n-арной операцией q(x1,..., xn): AnA называется nарной квазигруппой порядка |A|, если в уравнении x0 = q(x1,..., xn) любые n элементов из x0, x1,..., xn однозначно задают оставшийся элемент. В этом случае, согласно принятым в литературе обозначениям, n-арной квазигруппой порядка |A| называют также операцию q. Как следует из определения, n-арная квазигруппа обратима по каждому из n аргументов (в случае конечного множества A это свойство можно взять за определение), причём обратные функции также являются n-арными квазигруппами. n-Арная квазигруппа называется разделимой, если она представляется в виде бесповторной суперпозиции квазигрупп меньшей арности, где порядок переменных в суперпозиции не обязан совпадать с исходным порядком аргументов квазигруппы. Подфункция n-арной квазигруппы, полученная фиксацией одной или нескольких переменных, является квазигруппой меньшей арности (размерности) и называется ретрактом исходной n-арной квазигруппы.

Таблица значений n-арной квазигруппы называется латинским n-кубом. Известно, что любой латинский прямоугольник дополняется до латинского квадрата (теорема Кёнига Холла). В работах Кочела, Маккея и Ванлесса построены примеры латинских параллелепипедов любого порядка большего чем 4, не дополняемых до латинских гиперкубов.

Пусть Q(n,k) - число n-арных квазигрупп порядка k. Известно, что любая неразделимая n-арная квазигруппа порядка 4 является полулинейной. Число полулинейных квазигрупп также было вычислено ранее. При помощи теоремы о классификации получена рекуррентная формула для чисел Q(n,4). В этом направлении получены следующие результаты:

1.1. Доказано, что если все (n–2)- и (n–1)-мерные ретракты n-арной квазигруппы порядка p разделимы, то и сама квазигруппа является разделимой. Если число p является простым, то для разделимости n-арной достаточно разделимости всех её (n–1)-мерных ретрактов.

1.2. Доказано, что любой набор попарно совместимых (нигде не совпадающих) nарных квазигрупп порядка 4 дополняется до (n+1)-арной квазигруппы. Другими словами, любой латинский параллелепипед размера 44... 4k, где k = 1,2,3 достраивается до латинского гиперкуба.

1.3. Доказано, что при любых n> 2 и k>4 справедливы неравенства ((k–3) (k–1)/2)n/2 < log2 Q(n,k) < ck(k–2)n, где ck не зависит от n. Таким образом, верхняя асимптотическая граница для чисел Q(n,k) улучшена при любых k > 4, нижняя – при нечётных k > 6.

1.4. Доказано, что бесконечномерная квазигруппа порядка 4 является разделимой (представимой в виде суперпозиции) или полулинейной на каждом смежном классе по множеству аргументов с конечным носителем. Предложена конструкция неизмеримых по Лебегу множеств, основывающаяся на бесконечномерных квазигруппах.

Далее будут продолжены исследования по асимптотической оценке числа n-арных квазигрупп порядков больших 4.

2. Совершенным кликосочетанием в k-значном n-мерном кубе называется разбиение вершин куба на непересекающееся одномерные грани. В булевом n-мерном кубе понятие совершенного кликосочетания совпадает с понятием совершенного паросочетания. Совершенное кликосочетание называется точным, если в каждой двумерной грани содержится ровно один элемент кликосочетания.

Булевозначная функция называется корреляционно-иммунной порядка m, если её единицы равномерно распределены по граням размерности n–m. Булевозначная функция называется совершенной раскраской, если её единицы регулярно распределены по шарам радиуса 1, а именно количество единиц в шаре зависит только от значения функции в центре шара. Бент-функциями называются булевы функции максимально удалённые от множества линейных функций. Компонентой функции будем называть множество вершин, на котором функция отличается от другой функции с теми же параметрами.

Получены следующие результаты:

2.1. Доказано, что число совершенных кликосочетаний в k-значном n-мерном кубе выражается как k-мерный перманент массива смежности некоторого гиперграфа. Вычислен порядок логарифма числа совершенных кликосочетаний в k-значном n-мерном кубе равный knln(n) при любом натуральном k и n. Построены точные кликосочетания при k равном степени двойки и n=2k.

2.2. Показано, что для любого из перечисленных комбинаторных объектов мощность компоненты в промежутке между 2k и 2k+1 может принимать только значения вида 2k+1- 2p, где p принимает значения между 0 и k, а 2p - минимальная мощность компоненты для комбинаторного объекта с теми же параметрами. Для бент-функций доказано существование компонент любой мощности из данного спектра. Для совершенных раскрасок с некоторыми параметрами и корреляционно-иммунных функций найдены компоненты некоторых из указанных выше мощностей.

3. Спектром гамильтонова цикла (кода Грея) в булевом n-мерном кубе называется набор a = (a1, a2,..., an), где ai – число рёбер i-го направления в цикле. Известны необходимые условия существования кода Грея со спектром a: числа ai чётные и для любого k = 1,..., n сумма k произвольных компонент набора a не меньше чем 2k. Задача состояла в том, чтобы выяснить, являются ли эти необходимые условия на спектр гамильтонова цикла достаточными для существования кода Грея с таким спектром. Нами предложено асимптотическое решение этой задачи, а именно, доказано, что любой допустимый набор является спектром гамильтонова цикла в любом булевом n-кубе, если это верно для булева N-куба при некотором достаточно большом N. В доказательстве применяется конструкция гамильтонова цикла, использующая представление булева n-куба как декартова произведения кубов размерности k и n – k.. Отметим, что известно несколько способов построения кодов Грея с различными свойствами, в частности, построены гамильтоновы циклы с максимально равномерным (для фиксированной размерности) спектром, найден порядок логарифма числа различных кодов Грея в булевом n-кубе, определена асимптотика логарифма этого числа (при n ).

3.1. Булевым n-кубом называется множество Qn двоичных слов длины n, а также граф GQn, вершинами которого являются элементы Qn, и пара вершин смежна, если и только если соответствующие слова различаются ровно в одной позиции. Рассмотрим гамильтонов цикл в GQk, состоящий из рёбер непересекающихся совершенных паросочетаний P1 и P2, и вложим паросочетание P1 в GQn. Так как каждой вершине из GQk в декартовом произведении GQk GQnk соответствует булев (n k)-куб, каждому ребру из P1 можно поставить в соответствие пару параллельных (n k)-кубов, т. е. один (n k + 1)-куб. Заменим каждое ребро v P1 гамильтоновым циклом Hv в (n k + 1)-кубе, проходящим через это ребро. Удалив P из объединения P2 и циклов Hv, v P1, получим новый гамильтонов цикл в GQk GQnk = GQn. Если паросочетание со спектром (b1,..., bk) и хотя бы один из циклов в GQnk+1 имеют полный ранг, то в результате конструкции можно получить гамильтонов цикл полного ранга.

Основным результатом является следующая Теорема. Существует такое число N, что если любой допустимый целочисленный набор длины N является спектром некоторого гамильтонова цикла (полного ранга в случае, > 2k при любом k < N), то для любого целого n > 2 любой допустимый целочискогда ленный набор длины n является спектром некоторого гамильтонова цикла в GQn.

3.2. Под q-ичной параллельно-последовательной контактной схемой (-схемой) понимается обычная (двоичная) -схема, контактам которой приписаны символы xi, i = 1,..., n;

= 0, 1,..., q1. При этом символом xi является не булева переменная или её отрицание, а функция от xi, определённая на Bq = {0, 1,..., q 1} и принимающая значения из {0, 1}.

Значение функции xi равно 1, если xi =, и равно 0, если xi. Для определённых таким образом переменных естественно ввести операции дизъюнкции и конъюнкции. Поэтому любой обобщённой -схеме будет соответствовать формула, сложность которой определяется числом вхождений в неё переменных. Функция f : Bqn {0, 1} проводимости q-ичной -схемы определяется по аналогии с двоичным случаем: по определению q-ичная -схема реализует функцию f(x1,..., xn) =, где дизъюнкция берётся по всем простым (без самопересечений) цепям, соединяющим полюсы схемы, а KC – это конъюнкция всех функций,…,, приписанных контактам цепи C. Как и в двоичном случае, мы говорим, что контакт, помеn ченный xi, замкнут на наборе (1,..., n) Bq, если i =, и разомкнут в противном случае. Сложностью L(S) q-ичной -схемы S называется число контактов в S. Сложностью L(f) q-ичным -схемам, реализующим f. На множестве Bqn определим следующую функцию (линейную функцию, существенно зависящую от всех своих переменных):

Установлено, что сложность реализации в классе обобщённых (троичных) -схем троичного счётчика кратности 3, зависящего от трёх переменных, равна 18, т.е. L (3(x1, x2, x3)) = 18.

Доказательство неравенства L (3(x1, x2, x3)) 18 опирается на подход Храпченко В. М. к получению нижних оценок сложности -схем.

все i. Для слова определим число R(i) = 0.i i+1…. Отображение h : называется морфизмом, если h(xy) = h(x)h(y) для любых слов x, y – неподвижная точка морфизма, если () =. Всякий морфизм однозначно определяется образами символов алфавита, которые мы назовем блоками. Морфизм называется равноблочным, если его блоки имеют одинаковую длину. Морфизм : называется маркированным, если его блоки имеют вид (ai) = bi xci, где x – произвольное слово, а bi и ci – символы алфавита, причем все bi и все ci различны. В дальнейшем рассматриваются только маркированные равноблочные морфизмы с длиной блоков l. Отметим, что для всех неподвижных точек () = таких морфизмов существует число L такое, что любое подслово слова длины не менее L однозначно разбивается на блоки. Определим функцию : R \ {(a, a) | a R} {}, которая двум различным действительным числам ставит в соответствие их отношение.

Равноблочный морфизм : {0, 1} {0, 1} будем называть сравнимым, если его неподвижная точка = () удовлетворяет следующему условию: пусть i = j, где i i (mod l), j j (mod l) и 0 i, j l 1, причем i и j фиксированы. Если i j или если i и j лежат в блоках разного типа в правильном разбиении, то отношение (R(i), R(j)) определено однозначно. Следующие три утверждения содержат условие, по которому можно определить, является ли маркированный морфизм сравнимым.

Утверждение 1. Пусть неподвижная точка маркированного равноблочного морфизма, причем (0) = A, (1) = B. Тогда 1) если 0u1 является подсловом A или B, причем A = 0u0x, где x некоторое слово, то не является сравнимым морфизмом;

2) если 1u0 является подсловом A или B, причем B = 1u1x, где x некоторое слово, то не является сравнимым морфизмом.

Утверждение 2. Пусть неподвижная точка маркированного равноблочного морфизма, причем (0) = A, (1) = B. Тогда 1) если 0u является суффиксом A или B, причем A = 0u0x, где x некоторое слово, то не является сравнимым морфизмом;

2) если 1u является суффиксом A или B, причем B = 1u1x, где x некоторое слово, то не является сравнимым морфизмом.

Утверждение 3. Пусть неподвижная точка маркированного равноблочного морфизма, для которого не выполнены условия утверждений 1 и 2. Тогда сравнимый морфизм.

3.4. Пусть бесконечное вправо непериодическое слово над алфавитом. Тогда определим бесконечную перестановку, порождаемую словом, как упорядоченную тройку