Описано строение множества примитивных наборов натуральных чисел и установлены их основные свойства. С использованием понятий тупиковости и k-минимальности построен алгоритм перечисления примитивных наборов чисел, не ревышающих заданного числа m. Предложены алгоритмы определения показателя примитивности ориентированного конечного графа с помощью поиска в глубину на графе и возведения в степень матрицы смежности вершин и оценена их вычислительная сложность.
Скачать электронную версию публикации
Загружен, раз: 108
- Title О примитивных наборах натуральных чисел
- Headline О примитивных наборах натуральных чисел
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(16)
- Date:
- DOI
Ключевые слова
exponent, subexponent, primitive graph, primitive matrix, primitive system of natural numbers, субэкспонент, экспонент, примитивный граф, примитивная матрица, примитивный набор натуральных чиселАвторы
Ссылки
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. №2. С. 150-159.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. S. 642-648.
Лахно А. П. Поиск в глубину и его применение // Московские олимпиады по информатике. М.: МЦНМО, 2006.
Порублев И. Н., Ставровский А. Б. Алгоритмы и программы. Решение олимпиадных задач. М.: Вильямс, 2007
Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
Rosser B. The n-th prime is greater than n logn // Proc. London Math. Soc. 1939. V. 45. P.21-44.
Арнольд В. И. Экспериментальное наблюдение математических фактов. М.: МЦНМО, 2006.
Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000.
Биркгоф Г. Теория решеток. М.: Наука, 1984.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(11). С. 101-112.
О примитивных наборах натуральных чисел | Прикладная дискретная математика. 2012. № 2(16).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 210