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