Том 9, серия 1, номер 1, 2002 г., Стр. 59-83

УДК 519.17
С. В. Сорочан
Об энтропии композиций наследственных классов цветных графов

Аннотация:
Для конечного множества $Q =\{1,2,\dots,q\}$ рассматриваются $q$-цве́тные графы, получающиеся в результате раскрашивания ребер полного неориентированного графа в $q$ цветов. Для наследственных классов цветны́х графов, т.е. классов, замкнутых относительно удаления и переименования вершин, исследуется поведение энтропии – предела при $n\to\infty$ отношения логарифма по основанию $q$ числа $n$-вершинных $q$-графов, принадлежащих классу, к логарифму по основанию $q$ числа всех $n$-вершинных $q$-графов. Рассмотрены некоторые специальные наследственные классы $q$-графов, названные композициями, и получены значения, которые может принимать энтропия таких классов. Приведены основные свойства так называемых регулярных композиций наследственных классов $q$-графов.
Библиогр. 5.

Сорочан С. В. ¹
1. Нижегородский государственный университет, фак. вычисл. математики и кибернетики,
пр. Гагарина, 23, корп. 2, 603600 Нижний Новгород, Россия

Статья поступила 25 апреля 2001 г.
Исправленный вариант — 3 декабря 2001 г.