Том 7, серия 1, номер 4, 2000 г., Стр. 20-28
УДК 519.17
В. Е. Алексеев, С. В. Сорочан
Об энтропии наследственных классов ориентированных графов
Аннотация:
Рассматривается энтропия наследственных классов ориентированных графов (классов орграфов, замкнутых относительно удаления и переименования вершин), определяемая для класса$\mathscr X$ как предел отношения логарифма числа графов с$n$ вершинами из$\mathscr X$ к логарифму числа всех ориентированных графов с$n$ вершинами. Доказано, что область значений энтропии наследственных классов орграфов является разрывным множеством: если энтропия такого класса положительна, то она не может быть меньше чем 1/4. Охарактеризованы минимальные по включению наследственные классы орграфов, имеющие энтропию 1/4.
Библиогр. 5.
Алексеев В. Е. 1
Сорочан С. В. 1
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603600 Нижний Новгород, Россия
е-mail: ave@uic.nnov.ru
Статья поступила 22 февраля 2000 г.
Исправленный вариант — 20 апреля 2000 г.
