Том 16, номер 5, 2009 г., Стр. 19-25
УДК 519.17
В. Е. Алексеев, С. В. Сорочан
Об энтропийно минимальных наследственных классах цветных графов
Аннотация:
Рассматриваются наследственные классы графов с раскрашенными рёбрами. Класс называется энтропийно минимальным, если он не содержит собственных наследственных подклассов с тем же значением энтропии (логарифмической плотности). Для обыкновенных графов известно, что при любых фиксированных $a$ и $b$ класс, состоящий из всех графов, множество вершин которых можно разбить на $a$ клик и $b$ независимых множеств, является энтропийно минимальным. Доказывается обобщение этого утверждения для цветных графов.
Библиогр. 5.
Ключевые слова: наследственный класс, энтропия, энтропийно минимальный класс.
Алексеев Владимир Евгеньевич 1
Сорочан Сергей Владимирович 1
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603950 Нижний Новгород, Россия
е-mail: ave@uic.nnov.ru, svs-05@mail.ru
Статья поступила 16 апреля 2008 г.
Исправленный вариант — 8 мая 2009 г.
