Для n-вершинного сильносвязного орграфа оценена длина кратчайшего полного пути и, при наличии петли в графе, экспонент матрицы смежности вершин. Получена полиномиальная оценка субэкспонента системы матриц смежности вершин n-вершинных графов Гй,..., Гс, объединение которых сильно связно. Полученные результаты могут использоваться для исследования существенных переменных координатных функций, определяющих композиции преобразований множества конечных слов.
Скачать электронную версию публикации
Загружен, раз: 75
- Title СВОЙСТВА ПУТЕЙ В ГРАФАХ И МУЛЬТИГРАФАХ
- Headline СВОЙСТВА ПУТЕЙ В ГРАФАХ И МУЛЬТИГРАФАХ
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(7)
- Date:
- DOI
Ключевые слова
полный путь, кратчайший путь, экспонент, субэкспонент, full path, shortest path, exponent, subexponentАвторы
Ссылки
Фомичёв В. М. Методы дискретной математики в криптологии. М.: ДИАЛОГ-МИФИ, 2010. 424 с.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002. 816 с.
Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.
Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.
Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. 480 c.
<http://dic.academic.ru> - Словарь терминов теории графов.
Берж К. Теория графов и её применение. М.: ИЛ, 1962. 320 с.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5. Вып. 2. С. 150-159.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52 P. 642-648.
СВОЙСТВА ПУТЕЙ В ГРАФАХ И МУЛЬТИГРАФАХ | Прикладная дискретная математика. 2010. № 1(7).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 180