Условия примитивности и оценки экспонентов множеств ориентированных графов

doi:10.17223/20710410/35/8

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Условия примитивности и оценки экспонентов множеств ориентированных графов	605 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/35/8

#Виландта граф

#примитивное множество матриц

#экспонент графа

Title: Условия примитивности и оценки экспонентов множеств ориентированных графов
Title: Conditions of primitivity and exponent bounds for sets of digraphs
Creator: Авезова, Яна Эдуардовна
|
Фомичев, Владимир Михайлович
Date: 2017
DOI: 10.17223/20710410/35/8
Description: Исследованы вопросы минимизации заданного примитивного множества неотрицательных матриц порядка n (n-вершинных орграфов), где минимизация понимается как определение минимальных примитивных подмножеств. Получен универсальный критерий примитивности множества орграфов Г = {Г1,..., Гр}, p > 1, выраженный через характеристики мультиграфа Г1 U ... U Гр, в котором каждая дуга орграфа Г помечена символом i, i = 1, ...,p. Показано, что задача распознавания примитивности множества орграфов алгоритмически разрешима. Для частного класса множеств, когда орграфы Г1,..., Гр содержат общее множество контуров, получен ряд достаточных условий примитивности множества Г. Для множества орграфов Г = {Г0,..., Гп-1}, где Г — граф с множеством вершин {0,..., n — 1}, имеющий гамильтонов контур (0,..., n — 1) и дугу (i, (i+l) mod n), где n ^ l > 1, i = 0,... ,n — 1, уточнён критерий примитивности (множество орграфов Г примитивное тогда и только тогда, когда НОД(п,1 — 1) = 1) и в случае примитивности получены оценки экспонента: n — 1 ^ expГ ^ 2n — 2. Минимальное примитивное подмножество множества Г, на котором достигается верхняя оценка экспонента, содержит не более n/d орграфов, где d = НОД(п, l).

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2017. № 35. С. 89-101
Language: rus

Created: 19-04-2017

1094 Visitors

927 Hits

172 Downloads

Журналы ТГУ Условия примитивности и оценки экспонентов множеств ориентированных графов