The length of the shortest full path in a strongly connected orgraph with n vertices is estimated. The exponent of the vertex incedent matrix of the graph with self-loop is estimated too. A polynomial estimate is obtained for the subexponent of the system of vertex incedent matrices of n-vertex graphs whose union is a strongly connected graph. These results can be used to investigate essential variables of the coordinate functions which define compositions of transformations of the set of finite words
Download file
Counter downloads: 73
- Title PROPERTIES OF PATHS IN GRAPHS AND MULTIGRAPHS
- Headline PROPERTIES OF PATHS IN GRAPHS AND MULTIGRAPHS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(7)
- Date:
- DOI
Keywords
полный путь, кратчайший путь, экспонент, субэкспонент, full path, shortest path, exponent, subexponentAuthors
References
Фомичёв В. М. Методы дискретной математики в криптологии. М.: ДИАЛОГ-МИФИ, 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.
PROPERTIES OF PATHS IN GRAPHS AND MULTIGRAPHS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2010. № 1(7).
Download full-text version
Download fileCounter downloads: 179