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

В статье рассматривается количественная характеристика классов графов – энтропия, представляющая собой предел отношения логарифма числа графов с $n$ вершинами из данного класса к логарифму числа всех графов с $n$ вершинами. Получено окончательное решение вопроса о возможных значениях энтропии для наследственных классов, т.е. классов, включающих в себя вместе с любым графом все его порожденные подграфы. Доказано, что решетка наследственных классов разбивается на счетное множество слоев, каждый из которых состоит из классов с определенным значением энтропии, и описаны минимальные элементы каждого слоя. Тем самым получен критерий, позволяющий во многих случаях легко находить значения энтропии, а для классов, определяемых конечными множествами запрещенных подграфов, – вычислять эти значения алгоритмически. Это иллюстрируется рядом примеров.