Российская академия наук
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ
ИНСТИТУТ МАТЕМАТИКИ ИМ. С.Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РАН
(ИМ СО РАН)
УДК 519.17, 519.72
№ госрегистрации 01201172121
Инв. №
УТВЕРЖДАЮ
И.о. директора член-корреспондент РАН _ Гончаров С.С.
«_» 2012 г.
ОТЧЕТ
О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ
В рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы по государственному контракту № 14.740.11. шифр заявки 2010-1.5-502-001- по теме:
ФУНДАМЕНТАЛЬНЫЕ ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ В ПРОБЛЕМАХ РАСПРЕДЕЛЕНИЯ РАДИОЧАСТОТ В СЕТЯХ СОТОВОЙ СВЯЗИ, ТЕОРИИ КОДИРОВАНИЯ И
КРИПТОГРАФИИ, АНАЛИЗЕ СЕТЕЙ, ОБРАБОТКЕ И ПЕРЕДАЧИ ДАННЫХ
Наименование этапа: «Проведение фундаментальных исследований»(промежуточный, этап № 3) Руководитель НИР, д.ф.-м.н. _ А.В. Косточка Новосибирск
СПИСОК ИСПОЛНИТЕЛЕЙ
Косточка А.В. (Введение, Заклюрук. темы, в.н.с. ИМ СО РАН, чение, Приложения А-В, разделы д.ф.-м.н _ 1.4, 2, 5) отв. исполнитель темы, зав. лаб. Бородин О.В. (Реферат, ПрилоИМ СО РАН, д.ф-м.н. жения А-В, разделы 1.4, 2) _ гл.н.с. ИМ СО РАН, д.ф.-м.н. Кельманов А.В. (разделы 1.6, 2) _ в.н.с. ИМ СО РАН, д.ф.-м.н. Пяткин А.В. (раздел 1.6) _ в.н.с. ИМ СО РАН, д.ф.-м.н. Кротов Д.С. (разделы 1.1, 1.3, 2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Глебов А.Н. (разделы 1.5, 2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Добрынин А.А. (разделы 1.4, 2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Мельников Л.С. (раздел 1.4) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Потапов В. Н. (раздел 1.1, 2) _ с.н.с. ИМ СО РАН, к.ф.-м.н. Августинович С.В. (раздел 1.3, 2) _ Токарева Н.Н. (разделы 1.2, 2) с.н.с. ИМ СО РАН, к.ф.-м.н. _ с.н.с. ИМ СО РАН, к.ф.-м.н. Могильных И.Ю. (раздел 1.1, 1.3) _ аспирант ИМ СО РАН Замбалаева Д.Ж. (раздел 1.5) _ аспирант ИМ СО РАН Воробьев К.В. (раздел 1.3) _ аспирант НГУ Коломеец Н.А. (раздел 1.2) _ Отчет 35 с., 1 ч., 57 источников, 3 прил.
Тема: ФУНДАМЕНТАЛЬНЫЕ ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ В ПРОБЛЕМАХ
РАСПРЕДЕЛЕНИЯ РАДИОЧАСТОТ В СЕТЯХ СОТОВОЙ СВЯЗИ, ТЕОРИИ КОДИРОВАНИЯ И КРИПТОГРАФИИ, АНАЛИЗЕ СЕТЕЙ, ОБРАБОТКЕ И ПЕРЕДАЧИ ДАННЫХ
Ключевые слова: СОВЕРШЕННЫЕ РАСКРАСКИ; БУЛЕВЫ ФУНКЦИИ; БЕНТФУНКЦИИ; ТЕОРИЯ КОДИРОВАНИЯ; ДИСТАНЦИОННО РЕГУЛЯРНЫЕ КОДЫ; ТЕОРИЯ ГРАФОВ; РАСКРАСКА ГРАФОВ; ДЕКОМПОЗИЦИЯ ГРАФОВ; ИНВАРИАНТЫ
ГРАФОВ; КЛАСТЕРНЫЙ АНАЛИЗ.
Основным объектом исследования являются актуальные проблемы дискретной математики и ее приложений.Основной целью проекта является получение научных результатов мирового уровня, позволяющих укрепить позиции российской школы в области теоретических направлений в дискретной математике и информатике (методы эффективного кодирования и передачи информации, защита информации, анализ данных и распознавание образов, теория графов и ее приложения). Важной целью проведения работ является привлечение научных сотрудников, студентов и аспирантов к современным передовым методам и подходам в научноисследовательской работе в указанных областях, что будет способствовать повышению эффективности и устойчивости российских научных коллективов.
В процессе работы использовались классические и современные методы теории кодирования, методы теории графов, методы оптимизации и дискретного анализа, а также новые подходы, разработанные участниками проекта.
В результате фундаментальных поисковых исследований 3 этапа получены новые результаты мирового уровня.
1. Проведено исследование бент-функций на минимальном расстоянии от квадратичной бент-функции, получено описание всех таких бент-функций от 2k переменных.
2. Получен критерий, с помощью которого по параметрам совершенной 2-раскраски двоичного n-куба можно определить, является ли она кратным совершенным кодом заданного радиуса r > 1 некоторой кратности.
3. Доказано, что существуют сильно регулярные расширения графа Петерсена и графа решетки 3 3 с некоторыми параметрами и что не существует сильно регулярных расширений графов Шрикхандэ и Пэли.
4. Доказана NP-полнота задач разбиения последовательности векторов, содержащих конечное число элементов, по критерию минимума суммы квадратов расстояний.
5. Доказана справедливость гипотезы Вудала–Сеймура о наличии миноров полного двудольного графа Ks,t в (s + t)-хроматических графах для широкого диапазона параметра t для каждого фиксированного значения s.
6. Найден полиномиальный алгоритм для точной гармонической раскраски деревьев с большой максимальной степенью.
7. Получено исчерпывающее описание строения плоских графов в терминах звезд при младших вершинах. Опровергнута гипотеза Йендроля и Харанта.
8. Для n 425 и r < n описаны все n-вершинные гиперграфы с наибольшим числом ребер, не имеющие r-регулярных подграфов.
9. С точностью до логарифмического множителя найден порядок роста чисел Рамсея R(3, Krt) в r-униформных гиперграфах (треугольники против клик) для всех r 3.
10. Доказано, что аффинные функции – это в точности все те булевы функции, которые удалены от класса бент-функций на максимально возможное расстояние.
Степень внедрения – результаты исследований по проекту используются в образовательном процессе Новосибирского государственного университета и Новосибирского государственного университета экономики и управления при чтении общих и специальных курсов «Теория графов», «Дискретная математика», «Совершенные структуры», «Теория графов и алгоритмы», «Теория кодирования», «Анализ данных и распознавание образов».
Полученные результаты носят фундаментальный характер и, прежде всего, являются вкладом в общую математическую теорию.
Значимость и эффективность работ, помимо чисто научных результатов, заключается в подготовке молодых ученых, непосредственно участвовавших в работах наряду с признанными специалистами, и способствуют закреплению в сфере науки и образования научных и научно-педагогических кадров.
В развитии результатов этапа 3 в последующих работах этого направления следует ожидать формирование эффективного инструментария для исследования проблем дискретной математики, использующего новые подходы и постановки задач.
По ряду направлений в ходе исследований получены новые фундаментальные результаты мирового уровня, доложенные на научных форумах и подготовленные к печати.
ИМ СО РАН – Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук.
НГУ – Новосибирский государственный университет.
НГУЭиУ – Новосибирский государственный университет экономики и управления.
Поисковые исследования в области приложений бент-функций в криптографии и смежных областях, в теории кодирования информации, анализа структуры граф-моделей передачи информации и обработки данных Экстремальные структуры и построение кодов Булевы функции с экстремальными свойствами (бент-функции) Совершенные раскраски и коды Раскраска графов и смежные вопросы Оптимизационные задачи на графах и сетях Сложностные вопросы анализа данных и распознавания образов Полученные результаты Подготовка научно-методических материалов для публикаций Список использованных источников Приложение В. Программа научных семинаров по 3 этапу проекта Выполнение НИР по проекту направлено на проведение фундаментальных исследований в области теории кодирования и криптографии, обработке и передачи данных, анализа теоретико-графовых моделей в проблемах анализа структурных объектов. Основной целью НИР проекта является получение научных результатов мирового уровня, позволяющих укрепить позиции российской школы в области теоретических направлений в дискретной математике и информатике (методы эффективного кодирования и передачи информации, защита информации, анализ данных и распознавание образов, теория графов и ее приложения).
Одной из целей проведения работ является привлечение научных сотрудников, студентов и аспирантов к современным передовым методам и подходам в научно-исследовательской работе в указанных областях, что будет способствовать повышению эффективности и устойчивости российских научных коллективов.
Запланированная работа по этапу 3 включала поисковые исследования в области теории и приложений бент-функций в криптографии и смежных областях, в теории кодирования информации, анализа структуры граф-моделей передачи информации и обработки данных.
По результатам исследований подготовлены научно-методические материалы для публикаций.
1. Поисковые исследования в области приложений бент-функций в криптографии и смежных областях, в теории кодирования информации, анализа структуры граф-моделей передачи информации и обработки данных.
В рамках работ третьего этапа НИР основной акцент сделан на исследование конкретных проблем в теории графов и смежных вопросах теории кодирования, в области обработки, передаче и защите информации, в анализе данных и распознавании образов В отчете приведено описание работ по пунктам календарного плана в соответствии с техническим заданием.
1. Спектром гамильтонова цикла (кода Грея) в булевом n-мерном кубе называется набор a = (a1, a2,..., an), где ai – число рёбер i-го направления в цикле. Известны необходимые условия существования кода Грея со спектром a: числа ai чётные и для любого k = 1,..., n сумма k произвольных компонент набора a не меньше чем 2k. Задача состояла в том, чтобы выяснить, являются ли эти необходимые условия на спектр гамильтонова цикла достаточными для существования кода Грея с таким спектром. Нами предложено асимптотическое решение этой задачи, а именно, доказано, что любой допустимый набор является спектром гамильтонова цикла в любом булевом n-кубе, если это верно для булева N-куба при некотором достаточно большом N. В доказательстве применяется конструкция гамильтонова цикла, использующая представление булева n-куба как декартова произведения кубов размерности k и n – k. Этот результат анонсирован в [1]. Отметим, что известно несколько способов построения кодов Грея с различными свойствами, в частности, в [2, 3] построены гамильтоновы циклы с максимально равномерным (для фиксированной размерности) спектром. В [4] найден порядок логарифма числа различных кодов Грея в булевом n-кубе, а в [5] определена асимптотика логарифма этого числа (при n ).
Булевым 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.
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. Как и в двоичном случае, мы говорим, что контакт, помеченный xi, замкнут на наборе (1,..., n) Bqn, если i =, и разомкнут в противном случае. Сложностью L(S) q-ичной -схемы S называется число контактов в S. Сложностью L(f) функции f : Bqn {0, 1} в классе -схем называется, где минимум берётся по всем q-ичным -схемам, реализующим f. На множестве Bqn определим следующую функцию (линейную функцию, существенно зависящую от всех своих переменных):
Установлено, что сложность реализации в классе обобщённых (троичных) -схем троичного счётчика кратности 3, зависящего от трёх переменных, равна 18, т.е. L (3(x1, x2, x3)) = 18.
Доказательство неравенства L (3(x1, x2, x3)) 18 опирается на подход Храпченко В. М. к получению нижних оценок сложности -схем [6-11].
3. Бесконечное вправо слово над алфавитом – это слово вида = 123…, где все ется морфизмом, если 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. Тогда сравнимый морфизм.
Пусть бесконечное вправо непериодическое слово над алфавитом. Тогда определим бесконечную перестановку, порождаемую словом, как упорядоченную тройку = N, 0 удовлетворяет cr r/e, когда r. Значения cr улучшают и обобщают некоторые ранее известные результаты, которые используют известную теорему Атья, Комлоса, Принса, Спенсера и Семереди. Наше более короткое доказательство использует метод Ширера и Алона. Полученная нами оценка близка к наилучшей в том смысле, что для каждого r 2 и всех значений d N, существует бесконечно много гиперграфов Hn таких, что где br > 0 зависит только от r. Кроме того, для многих значений d показано, что br cr, когда. Поэтому результат почти точен для r. Также указано приложение результатов к чисr лам Рамсея для гиперграфов, связанных с независимыми окрестностями.
9. Известный результат в теории Рамсея говорит, что порядок роста чисел Рамсея 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 происходит скачок, а потом ситуация не меняется. Получены также оценки на некоторые другие числа Рамсея для гиперграфов.
10. В работе [36] Харант и Йендроль дали описание строения плоских графов в терминах звезд при младших вершинах, поглощающее ряд известных результатов в этой области. Там же была сформулирована гипотеза об идеальном описании такого рода. Ранее Бородиным и Ивановой были построены два класса контрпримеров к данной гипотезе. Сейчас получено описание конструкции, в котором все параметры являются неулучшаемыми 11. Пусть плоский граф G G(S) образован суперпозицией множества S простых замкнутых кривых на плоскости в общем положении, т.е. кривые не имеют самопересечений, не касаются друг друга, и никакие три кривые не имеют общей точки. Вершины графа G соответствуют точкам пересечения кривых из S, а ребра — дугам кривых, соединяющим соседние точки пересечения. Построенные таким образом 4–регулярные плоские графы называются графами Грцша–Закса. Вероятно, Г. Грцш в 50-х годах прошлого столетия был первым, кто исследовал задачу раскраски графов, образованных пересечениями кривых на плоскости. Если все кривые являются окружностями, то соответствующие графы называются графами Кёстера. Ранее в работах участников проекта были опровергнуты некоторые гипотезы о хроматическом числе таких графов, построены новые 4хроматические и 4-критические графы Грёцша-Закса [37-45]. Трудной проблемой в этой области является построение 4-хроматических и 4-критических графов Кёстера. Построен новый 4хроматический граф Кёстера на 32 вершинах, образованный пересечением 7 кривых на плоскости.
Этот граф является вершинно 4-критическим (т.е. удаление любой вершины уменьшает хроматическое число графа), но не реберно 4-критическим (четыре ребра являются не критическими).
Рассмотрена несимметричная задача о двух коммивояжерах на максимум, заключающаяся в нахождении двух реберно непересекающихся ориентированных гамильтоновых циклов максимального веса в полном ориентированном графе. Данная задача является обобщением классической задачи коммивояжера на максимум, а также модификацией симметричного случая задачи о двух коммивояжерах на максимум, который активно исследуется в последнее время. Известно, что задача коммивояжера и все содержательные варианты задачи о двух коммивояжерах NP-полны. Поэтому представляет интерес вопрос о выделении полиномиально разрешимых подклассов этих задач и о построении эффективных приближенных алгоритмов их решения с гарантированными оценками точности. Например, для симметричной задачи одного коммивояжера на максимум наилучший известный алгоритм имеет гарантированную асимптотическую оценку точности 25/33 [46], а для задачи о двух коммивояжерах на максимум – оценку точности 7/9 [47]. Для несимметричной задачи коммивояжера на максимум в работе [48] построен алгоритм с гарантированной оценкой точности 2/3. Нами получен аналогичный результат для задачи о двух коммивояжерах. А именно, для несимметричной задачи о двух коммивояжерах на максимум построен алгоритм, имеющий асимптотическую оценку точности 2/3 и оценку временной сложности O(n3), где n – число вершин графа. Как и алгоритм в [47], данный алгоритм основан на построении специальной раскраски ребер графа и на последующем выделении пары реберно непересекающихся частичных туров достаточно большого веса.
1.6. Сложностные вопросы анализа данных и распознавания образов Исследовались дискретные экстремальные задачи выбора из последовательности векторов евклидова пространства, состоящей из конечного числа членов, подпоследовательности элементов близких по критерию минимума суммы квадратов расстояний при наличии ограничений на номера выбираемых векторов. Цель исследования – анализ алгоритмической сложности этих задач. Полученные результаты дополняют работу [49], где было установлено, что к числу NP-трудных задач относятся следующие тесно связанные между собой оптимизационные задачи кластерного анализа и выбора подмножества в конечном множестве векторов евклидова пространства.
Задача VS-1 (Vector Subset 1).
подмножество C Y векторов такое, что целевая функция максимальна, при ограничении |C | M на мощность подмножества C.
Задача VS-2 (Vector Subset 2).
подмножество C Y векторов такое, что целевая функция где y (C ) y, минимальна, при ограничении |C | M на мощность искомого подyC множества.
«