|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Прикладная теория графов
Свойства минимальных примитивных орграфов
В. М. Фомичев Финансовый университет при Правительстве Российской Федерации, ООО "Код безопасности", г. Москва, Россия
Аннотация:
При $n\ge4$ доказано, что сложность определения всех $n$-вершинных минимальных примитивных орграфов, являющихся частью заданного примитивного $n$-вершинного орграфа $\Gamma$, совпадает со сложностью распознавания монотонной булевой функции от $s$ переменных, где $s$ – число дуг $(i,j)$ в $\Gamma$, таких, что полустепень исхода вершины $i$ и полустепень захода вершины $j$ превышают 1. Установлено, что при $n\ge4$ все примитивные $n$-вершинные орграфы с числом дуг $n+1$ являются минимальными и имеются минимальные примитивные $n$-вершинные орграфы с числом дуг от $n+2$ до $2n-3$. Описаны минимальные примитивные $n$-вершинные орграфы с числом дуг $n+1$ и $n+2$.
Ключевые слова:
примитивная матрица, примитивный орграф, сильносвязный орграф.
Образец цитирования:
В. М. Фомичев, “Свойства минимальных примитивных орграфов”, ПДМ, 2015, № 2(28), 86–96
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm503 https://www.mathnet.ru/rus/pdm/y2015/i2/p86
|
Статистика просмотров: |
Страница аннотации: | 215 | PDF полного текста: | 90 | Список литературы: | 54 |
|