Preview

Моделирование и анализ информационных систем

Расширенный поиск

Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника

Полный текст:

Аннотация

Исследуется связь между классом гиперграфов специального вида и свойствами точек релаксаций $M_{n,k}$ разрезного многогранника. Устанавливается, что при достаточно больших $n$ в многогранниках $M_{n,4}$ и $M_{n,5}$ имеются точки, в любом разложении которых по вершинам многогранника $M_{n,3}$ нет ни одной целой вершины.

Об авторе

Андрей Валерьевич Николаев
Ярославский государственный университет им. П.Г. Демидова
Россия


Список литературы

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

3. Бондаренко В.А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем: Сб. науч. тр. Ярославль: Яросл. гос. ун-т., 1987. С. 133 - 134.

4. Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.

5. Padberg M.V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139 - 172.

6. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.

7. Бондаренко В.А., Урываев Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика. 2007 №6. С. 18 - 23.

8. PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, <http://www.zib.de/Optimization/Software/Porta/>


Для цитирования:


Николаев А.В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника. Моделирование и анализ информационных систем. 2011;18(3):82-100.

For citation:


Nikolaev A.V. Hypergraphs of Special Type and CUT Polytope Relaxations Properties Analysis. Modeling and Analysis of Information Systems. 2011;18(3):82-100. (In Russ.)

Просмотров: 87


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)