RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2022, выпуск 15, страницы 105–107 (Mi pdma589)

Эта публикация цитируется в 1 статье

Прикладная теория кодирования и графов

О конечной динамической системе всех возможных ориентаций данного графа со всеми достижимыми и недостижимыми состояниями

А. В. Жаркова

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского

Аннотация: Рассматривается конечная динамическая система, состояниями которой являются все возможные ориентации данного графа, а эволюционная функция задаётся следующим образом: динамическим образом орграфа является орграф, полученный из исходного путём переориентации всех дуг, входящих в стоки, других отличий между исходным орграфом и его образом нет. Характеризуются системы, все состояния которых являются достижимыми и в которых есть недостижимые состояния; подсчитывается количество графов, образующих системы со всеми достижимыми состояниями; приводится таблица с количеством графов с числом вершин от одной до двенадцати, образующих системы со всеми достижимыми и недостижимыми состояниями.

Ключевые слова: граф, достижимое состояние, конечная динамическая система, недостижимое состояние, ориентированный граф, отказоустойчивость, эволюционная функция.

УДК: 519.1, 004.05

DOI: 10.17223/2226308X/15/24



© МИАН, 2024