Preview

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

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

О числе фасет 2-смежностного многогранника

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

Аннотация

Многогранник Р называется 2-смежностным, если любые две его вершины образуют ребро (1-грань) многогранника P. Высказывается предположение, что число fо(Р) вершин такого многогранника не превосходит числа его фасет (граней наибольшей размерности). Доказывается справедливость утверждения для случаев d < 7 и fо(Р) < d + 6, где d - размерность многогранника.

Об авторе

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


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

1. Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогран-никах // Дискретная математика. 2008. Т. 20, № 1. С. 64-69.

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

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

4. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптими¬зация. М.: Наука, 1981. 344 с.

5. Aichholzer O. Extremal properties of 0/1-polytopes of dimension 5 // G. Ziegler and G. Kalai, editors, Polytopes - Combinatorics and Computation. Birkhauser, 2000. P. 111-130.

6. Avis D. lrslib Ver 4.2 is a self-contained ANSI C implementation as a callable library of the reverse search algorithm for vertex enumeration/convex hull problems: http://cgm.cs.mcgill.ca/~avis/C/lrs.html

7. Barnette D. The minimum number of vertices of a simple polytope // Israel J. Math. 1971. V. 10. P. 121-125.

8. Barnette D. A proof for the lower bound conjecture for convex polytopes // Pacific J. Math. 1973. V. 46. P. 349-354.

9. Bisztriczky T. On sewing neighbourly polytopes // Note di Matematica. 2000/2001. V. 20, № 1. P. 73--80.

10. Blind G. and Blind R. Convex polytopes without triangular faces // Isr. J. Math. 1990. V. 71. P. 129-134.

11. Gale D. Neighboring vertices on a convex polyhedron // Linear inequalities and related systems / Eds. H.W. Kuhn, A.W. Tucker. Princeton, New Jersey: Princeton University Press, 1956.

12. Henk M., Richter-Gebert J. and Ziegler G. Basic properties of convex polytopes // J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 16. Chapman & Hall/CRC Press, Boca Raton, second edition, 2004. P. 355-382.

13. Kovalev M., Maurras J.-F., Vaxes Y. On the convex hull of 3-cycles of the complete graph // Pesquisa Operacional. 2003. V. 23, № 1. P. 99-109.

14. Onn S. Geometry, Complexity, and Combinatorics of Permutation Polytopes // J. Comb. Theory, Series A. 1993. V. 64, № 1. P. 31-49.

15. Shemer I. Neighborly polytopes // Isr. J. Math. 1982. V. 43. P. 291-314.


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


Максименко А.Н. О числе фасет 2-смежностного многогранника. Моделирование и анализ информационных систем. 2010;17(1):76-82.

For citation:


. On the number of facets of a 2-neighborly polytope. Modeling and Analysis of Information Systems. 2010;17(1):76-82. (In Russ.)

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


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


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