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

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

В. Е. Алексеев


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

УДК: 519.1

Статья поступила: 02.09.1991

 Англоязычная версия: Discrete Mathematics and Applications, 1993, 3:2, 191–199

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

• 
•