Улучшенная формула универсальной оценки экспонента орграфа В. М. Фомичев
Material type:
ArticleSubject(s): ориентированные графы | Фробениуса числа | экспонентаGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика. Приложение № 11. С. 16-20Abstract: Улучшена формула универсальной оценки экспонента n-вершинного примитивного орграфа, данная А. Далмэджем и Н. Мендельсоном (1964) с использованием множества контуров, длины которых взаимно простые. Предложенная формула использует в орграфе множество контуров C с множеством длин L(C) == {ll , ... ,lm}, где d = (ll , . . .,lm) A 1, и множество длин кратчайших путей { Г1^(С) : s = 0,..., d—1} из вершины i в вершину j, проходящих через множество контуров С и образующих полную систему вычетов по модулю d. Показано, что exp Г ^ 1 + F (L(C)) + R(C), где F(L) = d ■ F (li/d,..., lm/d); F (ai,..., am) — число Фробениуса; R(C) = max max { г ^ (С ) } . Указан класс орграфов с множеством
(М) s вершин {0,..., 2k — 1}, k > 2, для которых предложенные оценки экспонентов лучше известных на величину k — 2.
Библиогр.: 11 назв.
Улучшена формула универсальной оценки экспонента n-вершинного примитивного орграфа, данная А. Далмэджем и Н. Мендельсоном (1964) с использованием множества контуров, длины которых взаимно простые. Предложенная формула использует в орграфе множество контуров C с множеством длин L(C) == {ll , ... ,lm}, где d = (ll , . . .,lm) A 1, и множество длин кратчайших путей { Г1^(С) : s = 0,..., d—1} из вершины i в вершину j, проходящих через множество контуров С и образующих полную систему вычетов по модулю d. Показано, что exp Г ^ 1 + F (L(C)) + R(C), где F(L) = d ■ F (li/d,..., lm/d); F (ai,..., am) — число Фробениуса; R(C) = max max { г ^ (С ) } . Указан класс орграфов с множеством
(М) s вершин {0,..., 2k — 1}, k > 2, для которых предложенные оценки экспонентов лучше известных на величину k — 2.
There are no comments on this title.