Новая универсальная оценка экспонентов графовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 3 мая 2017 г.
Аннотация:Получена новая универсальная оценка экспонентов n-вершинных примитивных орграфов через характеристики содержащихся в орграфе контуров C_1,...,C_k длины l_1,...,l_k соответственно, где (l_1,...,l_k)=1. Показано, что \exp\Gamma\le n(r+1)+g(l_1,...,l_k)+L, где r - число компонент связности орграфа C_1\cup...\cup C_k; g(l_1,...,l_k) - число Фробениуса; L - линейная комбинация длин определённых контуров орграфа \Gamma. Дано уточнение оценки для некоторых частных случаев. Приведены примеры оценок экспонентов орграфов. Полученная универсальная оценка для многих n-вершинных примитивных орграфов улучшает известные оценки. Порядок её величины варьируется от O(n) до O(n^2). Оценка принимает наибольшие значения порядка O(n^2), только если кратчайший контур примитивной системы имеет длину порядка O(n). На графах Виландта полученная оценка совпадает с оценкой Виландта.