Том 8, серия 1, номер 2, 2001 г., Стр. 52-62
УДК 519.172
А. Л. Пережогин, В. Н. Потапов
О числе гамильтоновых циклов в булевом кубе
Аннотация:
Показано, что при$n\to\infty$ логарифм числа разбиений$n$ -мерного булева куба$E^n$ на циклы равен$2^n(\ln n-1+o(1))$ и логарифм числа гамильтоновых циклов в$E^n$ не меньше$2^{n-1}(\ln n-1+o(1))$ . Доказано, что в$E^n$ каждое совершенное паросочетание, в котором содержатся рёбра не более$k$ направлений, дополняется до гамильтонова цикла при любом$n\geqslant n_0(k)$ .
Библиогр. 12.
Пережогин А. Л. 1
Потапов В. Н. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 6 февраля 2001 г.
