Том 10, серия 1, номер 1, 2003 г., Стр. 79-104

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

Аннотация:
Для конечного множества $Q=\{1,2,\dots,q\}$ рассматриваются $q$-цве́тные графы, получающиеся в результате раскрашивания ребер полного неориентированного графа в $q$ цветов. Проводится исследование ранее определенных регулярных композиций наследственных классов $q$-графов. Найдены нижняя и верхняя оценки значений энтропии этих классов. Введено понятие правильной композиции наследственных классов и доказано, что каждая регулярная правильная композиция является минимальным по включению классом среди композиций с заданным значением энтропии. Охарактеризованы минимальные по включению регулярные $(k+1)$-композиции, содержащие заданную регулярную $k$-композицию. Найдена взаимосвязь между простыми и сложными композициями, т.е. композициями, хотя бы одна секция которых сама является композицией наследственных классов. Установлено, что в области допустимых значений энтропии фрагментно замкнутых классов $q$-графов при $q>2$ существует бесконечное множество точек сгущения.
Библиогр. 3.

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

Статья поступила 20 января 2003 г.