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

ПДМ. Приложение, 2019, выпуск 12, страницы 176–179 (Mi pdma464)

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

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

А. В. Жаркова

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

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

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

УДК: 519.1

DOI: 10.17223/2226308X/12/49



Реферативные базы данных:


© МИАН, 2024