АЛГОРИТМЫ АНАЛИЗА ПРИМИТИВНОСТИ ОРИЕНТИРОВАННЫХ ГРАФОВ

С. Н. Кяжин, В. М. Фомичев

Аннотация


Построены алгоритмы определения показателя примитивности ориентированного конечного графа с помощью поиска в глубину на графе и с помощью возведения в степень матрицы смежности вершин. Оценена вычислительная сложность предложенных алгоритмов.

Ключевые слова


примитивный граф; примитивная матрица; показатель примитивности

Полный текст:

PDF

Литература


1 Лахно А. П. Поиск в глубину и его применение. // Московские олимпиады по информатике. М.: МЦНМО, 2006.

2 Порублев И. Н., Ставровский А. Б. Алгоритмы и программы. Решение олимпиадных задач. М.: И. Д. «Вильямс», 2007.

3 Wielandt H. Unzerlegbare nicht negative Matrizen. // Mathematische Zeitschrift. 1950. № 52. S. 642—648.

4 Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц.// Дискретная математика. 1993. № 2. С. 150-159.


Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.