ОТЗЫВ
официального оппонента на диссертационную работу «Анализ структуры циклов некоторых графов Кэли на симметрической группе», представленную на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 – «Дискретная математика и математическая кибернетика».
Актуальность темы диссертации.
Диссертация посвящена изучению циклов в некоторых графах Кэли на симметрической группе, а именно в Star графах и в Pancake графах. В частности изучаются циклы малой длины и гамильтоновы циклы, а также связанные с ними коды Грея. Данные вопросы представляют как теоретический, так и прикладной интерес, таким образом, тема диссертации является актуальной.
Содержание диссертации.
Во введении даются основные определения, и история вопроса.
В первой главе предложен подход описания циклов малой длины в Pancake графах и в Star графах, на основе их иерархического строения. Этот подход применен для описания циклов длины 6,7 и 8 в Pancake графах Pn при любых n>2 и для описания циклов длины 6 и 8 в Star графах Sn для любых n>2. Найдено число таких циклов, проходящих через каждую вершину, и общее число циклов для каждого из классов.
Во второй главе изучаются гамильтоновы циклы в Pancake графах. Предложена новая конструкция гамильтоновых циклов на основе введенного автором понятия независимых циклов. С помощью этой конструкции описаны все известные гамильтоновы циклы в Pancake графах Pn при любых n, а также найдены два новых гамильтоновых цикла в P4. Доказано несуществование почти всех таких циклов в графах Pn при n>4. Доказано необходимое условие существования жадных префикс-реверсальных кодов Грея.
В третьей главе получена асимптотическая оценка для числа циклов длины 2d в Star графах.
Работа содержит все необходимые определения и может читаться без обращения к дополнительным источникам. Доказательства утверждений полны и корректны, а результаты являются достоверными и обоснованными. Серьезных претензий к диссертации нет.
Замечания:
При этом текст диссертации имеет некоторые недостатки:
5 с. нет пояснения к понятию минимальный транспозиционный граф (в каком смысле минимальный).
8 с. задача проверки графа на гамильтоновость некорректно названа задачей коммивояжера (это задача поиска кратчайшего гамильтонова цикла во взвешенном графе).
12 с. «Известно, что каждый ℓ–цикл может быть представлен 2 ℓ формами (не обязательно различными)» (само понятие числа возможных представления подразумевает различность этих представлений).
14 с. неверное определение внешних ребер, то есть далее в работе используется другое понятие.
46 с. опечатка «основанных на основе независимых циклах в графе».
46-47с. упорядоченное множество обозначается фигурными скобками вместо круглых.
49 с. «В случае независимых 6–циклов, все неиспользованные ребра соответствуют префикс–реверсалу r4 » на самом деле не неиспользованные, а внешние ребра соответствуют этому реверсалу.
54 с. нет пояснения к фразе «существование доказано почти для всех n» (что происходит в остальных случаях непонятно).
Также присутствует некоторое количество незначительных опечаток.
Все основные результаты диссертации являются новыми, носят теоретический характер и представляют интерес для специалистов в области теории графов. Доказательства изложены подробно и ясно. Результаты диссертации докладывались автором на российских и международных конференциях и семинарах в Новосибирске, Екатеринбурге, Венгрии и Словении, в частности на конференциях по теории графов. Результаты опубликованы и известны специалистам. Автореферат полно и правильно отражает содержание диссертации.
Считаю, что диссертация «Анализ структуры циклов некоторых графов Кэли на симметрической группе» удовлетворяет критериям, установленным «Положением о порядке присуждения ученых степеней» , а ее автор заслуживает присуждения ему ученой степени кандидата физико-математических наук.
Официальный оппонент, кандидат физико-математических наук, доцент кафедры компьютерной безопасности и прикладной алгебры Федерального государственного бюджетного образовательного учреждения высшего образования «Челябинский государственный университет» |
___________________ |
Адрес организации: 454001,
Телефон: +7 (351) 799-71-01
E-mail: *****@***ru, *****@***ru
Подпись Шалагинова Леонида Викторовича заверяю, (должность) | () ___________________ |
