RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2000, том 7, выпуск 4, страницы 20–28 (Mi da276)

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

Об энтропии наследственных классов ориентированных графов

В. Е. Алексеев, С. В. Сорочан

Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: Рассматривается энтропия наследственных классов ориентированных графов (классов орграфов, замкнутых относительно удаления и переименования вершин), определяемая для класса $\mathscr X$ как предел отношения логарифма числа графов с $n$ вершинами из $\mathscr X$ к логарифму числа всех ориентированных графов с $n$ вершинами. Доказано, что область значений энтропии наследственных классов орграфов является разрывным множеством: если энтропия такого класса положительна, то она не может быть меньше чем 1/4. Охарактеризованы минимальные по включению наследственные классы орграфов, имеющие энтропию 1/4. Библиогр. 5.

УДК: 519.17

Статья поступила: 22.02.2000
Переработанный вариант: 20.04.2000



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


© МИАН, 2024