2009 O 2-смежностных многогранниках и конструкции Гейла Бродский А.Г. Задача Эрдеша – Секереша о пустых шестиугольниках на плоскости Кошелев В.А. <...> Об одном классе счетчиковых машин Кузьмин Е.В., Чалый Д.Ю. <...> Восстановление изображений, искажённых перспективным преобразованием Малков А.Н., Михайлов И.А., Штерн Г.П. <...> Признак абелевости группы нечетного порядка Казарин Л.С., Чанков Е.И. <...> О классах эквивалентности множеств Делоне Гарбер А.И. <...> On Erd´ os – Szekeres problem for empty hexagons in the plane Koshelev V.A. <...> П.Г. Демидова e-mail: alexey.brodskiy@gmail.com получена 13 октября 2008 Ключевые слова: 2-смежностный многогранник, конструкция Гейла, вероятность, плотность графа многогранника, труднорешаемые задачи Исследуются свойства предложенной Гейлом конструкции 2-смежностных многогранников. <...> Гейла [22], который предложил конструкцию, позволяющую, в частности, по некоторым системам n точек на сфере Sm−1 в Rm, где n m + 2, строить 2-смежностные многогранники в Rd, где d = n − m − 1. <...> 16, №2 (2009) и строго 2-смежностного многогранников условия, накладываемые на исходную систему n точек на сфере Sm−1, являются более прозрачными и удобными с точки зрения построения таких систем. <...> Представляют интерес и редуцированные варианты этой гипотезы [9, 11,12]: (G1) вероятность того, что при случайном выборе n точек a1, . . . , an на сфере Sd−1 выпуклый многогранник conv(a1, . . . , an) является 2-смежностным, быстро возрастает с увеличением d; (G2) вероятность того, что при случайном выборе n точек a1, . . . , an из множества вершин единичного куба Id = {0, 1}d ⊆ Sd−1 выпуклый многогранник conv(a1, . . . , an) является 2-смежностным, быстро возрастает с увеличением d. <...> Что касается гипотезы (G), то возможным подходом к ее доказательству Гейл считает сведение к гипотезе (G3) вероятность получения (строго) 2-смежностного многогранника в Rd с помощью конструкции Гейла (при случайном выборе n точек на сфере Sm−1) быстро возрастает <...>
Моделирование_и_анализ_информационных_систем_(МАИС)_№2_2009.pdf
ISSN 1818-1015
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
МОДЕЛИРОВАНИЕ И АНАЛИЗ
ИНФОРМАЦИОННЫХ СИСТЕМ
Том 16 № 2 2009
Основан в 1999 г.
Выходит 4 раза в год
Свидетельство о регистрации №019209 от 16.08.99
Государственного Комитета Российской Федерации по печати
Главный редактор
В.А. Соколов
Редакционная коллегия
С.М. Абрамов, О.Л. Бандман, В.А. Бондаренко, И.Б. Вирбицкайте,
С.Д. Глызин (зам. гл. ред.), М.Г. Дмитриев, В.Л. Дольников, В.Г. Дурнев,
А.В. Зафиевский, Л.С. Казарин, Ю.Г. Карпов, С.А. Кащенко, А.Ю. Колесов,
И.А. Ломазова, В.Э. Малышкин, В.А. Непомнящий, П.Г. Парфенов, Р.Л. Смелянский
Ответственный секретарь Е.А. Тимофеев
Адрес редакции: 150000, Ярославль, ул. Советская, 14
E-mail: mais@uniyar.ac.ru
Website: mais.uniyar.ac.ru
Научные статьи в журнал принимаются по электронной почте и на кафедре
теоретической информатики Ярославского государственного университета. Статьи
должны содержать УДК, аннотации на русском и английском языках и сопровождаться
набором текста в редакторе LaTEX. Плата с аспирантов за публикацию
рукописей не взимается.
-Ярославский государственный
университет им. П.Г. Демидова, 2009
c
Стр.1
СОДЕРЖАНИЕ
Моделирование и анализ информационных систем. Т. 16, №2. 2009
O 2-смежностных многогранниках и конструкции Гейла
Бродский А.Г.
Задача Эрдеша – Секереша о пустых шестиугольниках на плоскости
Кошелев В.А.
Об одном классе счетчиковых машин
Кузьмин Е.В., Чалый Д.Ю.
Свойства e-степеней ограниченно тотальных множеств
Рожков С.В.
Восстановление изображений, искажённых перспективным преобразованием
Малков А.Н., Михайлов И.А., Штерн Г.П.
Признак абелевости группы нечетного порядка
Казарин Л.С., Чанков Е.И.
О классах эквивалентности множеств Делоне
Гарбер А.И.
Правила для авторов
Информация о подписке
5
22
75
83
88
103
109
119
120
Редактор, корректор А.А. Аладьева. Редактор перевода Э.И. Соколова
Подписано в печать 05.06. 2009. Формат 60х841/8.
Усл. печ. л. 13,5. Уч.-изд. л. 10,5. Тираж 500 экз.
Отпечатано на ризографе. Ярославский государственный университет имени П. Г. Демидова,
150 000, Ярославль, ул. Советская, 14
Стр.2
ISSN 1818-1015
Ministry of Education and Science of the Russian Federation
Federal Education Agency
Yaroslavl Demidov State University
MODELING AND ANALYSIS
OF INFORMATION SYSTEMS
Volume 16 No 2 2009
Founded in 1999
4 issues per year
State Registration License No 019209 of 16.08.1999
Editor-in-Chief
V. A. Sokolov
Editorial Board
S.M. Abramov, O.L. Bandman, V.A. Bondarenko, I.B. Virbitskayte,
S.D. Glyzin (Deputy Editor-in-Chief ), M.G. Dmitriev, V.L. Dol’nikov,
V.G. Durnev, A.V. Zafievsky, L.S. Kazarin, Yu.G. Karpov,
S.A. Kashchenko, A.Yu. Kolesov, I.A. Lomazova,
V.E. Malyshkin, V.A. Nepomniaschy, P.G. Parfionov, R.L. Smeliansky
Responsible Secretary E. A. Timofeev
Editorial Office Address: Sovetskaya str., 14, Yaroslavl, 150000, Russia
E-mail: mais@uniyar.ac.ru
Website: mais.uniyar.ac.ru
-Yaroslavl Demidov State University, 2009
c
Стр.3
Contents
Modeling and Analysis of Information Systems. Vol. 16, No 2. 2009
On 2-neighborly polytopes and the Gale construction
Brodskiy A.G.
On Erd´
os – Szekeres problem for empty hexagons in the plane
Koshelev V.A.
On a class of counter machines
Kuzmin E.V., Chalyy D.J.
Properties of e-degrees of the bounded total sets
Rozhkov S.V.
Restoration of images distorted by the perspective transformation
Malkov A.N., Mikhaylov I.A., Shtern G.P.
A commutativity criterion for a group of odd order
Kazarin L.S., Chankov E.I.
On equivalence classes of separated nets
Garber A.I.
22
75
83
88
103
109
5
Стр.4
Модел. и анализ информ. систем. Т.16, №2 (2009) 5–21
УДК 519.1
O 2-смежностных многогранниках
и конструкции Гейла
Бродский А.Г.
Ярославский государственный университет им. П.Г. Демидова
e-mail: alexey.brodskiy@gmail.com
получена 13 октября 2008
Ключевые слова: 2-смежностный многогранник, конструкция Гейла,
вероятность, плотность графа многогранника, труднорешаемые задачи
Исследуются свойства предложенной Гейлом конструкции 2-смежностных
многогранников.
Введение
Как известно, вычислительную сложность задач комбинаторной оптимизации отражают
некоторые свойства графов многогранников, порождаемых этими задачами.
В частности, заметную роль играет плотность (т.е. максимальное количество попарно
смежных вершин) графов многогранников, которая служит нижней границей
временной трудоемкости алгоритмов из широкого класса, включающего большинство
известных комбинаторных методов. Оценки плотности полиэдральных графов
большого количества комбинаторных задач, полученные в работах [1–10,14,16–20],
показали, что эта характеристика экспоненциальна по размерности многогранников
для труднорешаемых задач и полиномиальна для полиномиально разрешимых.
Более того, полиэдральные графы задач о максимальном разрезе (см. [2, 20]), о
покрытии матрицы (см. [9]), о клике (вершинное покрытие, независимое множество)
(см. [6, 14]) являются полными. Напомним, что многогранники, у которых любые
две вершины смежны, называются 2-смежностными [13, 15, 23].
Существование уже в R4 2-смежностных многогранников со сколь угодно большим
числом вершин установил К. Каратеодори [21] в 1907 году. В 1956 г. этот факт
был «переоткрыт» в работе Д.Гейла [22], который предложил конструкцию, позволяющую,
в частности, по некоторым системам n точек на сфере Sm−1 в Rm,
где n m + 2, строить 2-смежностные многогранники в Rd, где d = n − m − 1.
Получаемые с помощью конструкции Гейла 2-смежностные многогранники имеют
некоторый специальный вид (в предлагаемой ниже терминологии это строго
2-смежностные многогранники). По сравнению с определениями 2-смежностного
5
Стр.5