Исследование количественных характеристик наследственных классов ориентированных и цветных графов

Содержанием большинства работ по теории графов и ее приложениям является изучение тех или иных классов графов (например, пленарных графов, лесов, двудольных графов, совершенных графов и т. д.). В последнее время представляет повышенный интерес рассмотрение не отдельных классов, а некоторых семейств классов, обладающих тем или иным общим свойством. Среди важных проблем теории графов, сама постановка которых выводит на такой уровень общности, можно выделить задачу количественного перечисления графов из заданной совокупности и их характеризации по определенной количественной мере.

При решении задачи количественного перечисления [34, 45, 55], а также связанных с ней проблем кодирования, декодирования графа и сжатия информации [1, 2, 7, 9, 23, 38, 39] определяющую роль играют мощностные характеристики рассматриваемого семейства. Выбор той или иной количественной меры приводит к проблеме описания ее области допустимых значений для классов графов из определенного семейства. Кроме того, в процессе решения этой проблемы возникает необходимость в исследовании еще нескольких связанных с ней задач, наиболее важными из которых являются выявление минимальных по включению среди классов с заданным допустимым значением меры, а также структурная и сложностная характеризация таких классов, т. е. характеризация в терминах запрещенных фрагментов и определение сложности распознавания.

В настоящей диссертации содержатся результаты исследования наследственных классов ориентированных и цветных графов, нацеленного на решение указанных выше проблем.

В работе рассматриваются два типа графов: ориентированные графы и не столь широко известные цветные графы, которые получаются в результате раскрашивания ребер обыкновенного полного графа в цвета из заданного множества. В качестве объекта исследования взяты наследственные классы графов указанных типов, т. е. классы графов, замкнутые относительно удаления и переименования вершин, а также определенные семейства таких классов. Повышенный интерес именно к наследственным классам обусловлен тем, что, с одной стороны, они образуют достаточно представительную совокупность (в работе [4] доказано, что семейство наследственных классов обыкновенных графов континуально, аналогичное утверждение справедливо и для семейств наследственных классов ориентированных и цветных графов), а, с другой стороны, допускают очень распространенный в теории графов способ описания — описание с помощью множества запрещенных порожденных подграфов. Выбор в качестве исследуемых объектов классов ориентированных и цветных графов также не случаен: ранее выше указанные задачи были поставлены и полностью решены [2, 4, б, 7, 9, 40] для наследственных классов обыкновенных графов, поэтому вполне естественно распространить эти задачи на классы, являющиеся более представительными и разнообразными по сравнению с классами обыкновенных графов. Кроме того, успешное решение задачи количественного перечисления графов, относящихся к более представительным типам, позволит провести сравнительный анализ с уже известными результатами для обыкновенных графов, а также выявить некоторые общие закономерности и установить индивидуальные особенности, которыми обладают полученные результаты и методы решения задач.

Изложенные в работе результаты относятся к двум направлениям: исследование количественных характеристик наследственных классов ориентированных и цветных графов, а также алгоритмические и сложностные вопросы распознавания ориентированных и цветных графов из наследственных классов.

При решении вопросов количественного анализа в работе принят асимптотический подход, основанный на понятии энтропии множества графов. Энтропия представляет собой «логарифмическую плотность» — предел отношения логарифма числа графов с п вершинами из данного множества к логарифму числа всех и-вершинных графов заданного типа. Существование этого предела является одним из общих свойств наследственных классов (существование энтропии наследственных классов обыкновенных графов было ранее установлено в работах [2, 4, 46], одним из результатов данной работы является доказательство существования энтропии наследственных классов ориентированных и цветных графов). Указанное свойство, а также некоторые другие свойства наследственных классов графов аналогичны свойствам инвариантных классов булевых функций, введенных и изученных С. В. Яблонским [38]. Однако между семействами наследственных классов графов и инвариантных классов булевых функций имеются и существенные различия. Так, С. В. Яблонский доказал, что параметр, аналогичный энтропии наследственных классов, для инвариантных классов может принимать любые значения из отрезка [0,1]. Позднее В. Е. Алексеев в работах [6, 40] установил, что множество допустимых значений энтропии наследственных классов обыкновенных графов счетно (оно состоит только из чисел вида 1 — доказал существование и дал исчерпывающее описание минимальных по включению классов с заданным значением энтропии (это один из основных результатов диссертации [9]).

В главе I настоящей диссертации исследуются вопросы, связанные с предельными теоремами теории графов [46, 47]. Здесь доказано существование энтропии наследственных классов ориентированных и цветных графов и установлено, что область ее значений для бесконечных классов каждого из этих двух типов является разрывным множеством: она либо равна нулю, либо не меньше, чем | для наследственных классов орграфов, и не меньше, чем \ogq2 для наследственных классов^{-цветных} графов. Затем найдено описание минимальных по включению наследственных классов графов рассматриваемых типов в слоях с нулевой и наименьшей поло? кительной энтропией и проведено сравнение с ситуацией в аналогичных слоях наследственных классов обыкновенных графов. На основе полученного описания этих минимальных классов возникает потребность в более пристальном изучении наследственных классов двудольных графов указанных типов. С этой целью в заключительной части главы I вводятся понятия двудольных энтропий наследственных классов двудольных ориентированных и цветных графов, доказывается теорема их существования и полностью описываются области их допустимых значений, являющиеся конечными множествами. Результаты главы I опубликованы в работах [11, 12, 24, 25, 43].

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

С другой стороны, результаты второй главы указывают на существенное отличие в поведении сложности распознавания на соответствующих друг другу наследственных классах обыкновенных и ориентированных графов.

Понятийный аппарат и результаты, полученные в главе III, открывают обширную область для дальнейших исследований, направленных на более глубокий анализ композиций наследственных классов. При этом наиболее перспективным видится изучение именно регулярных композиций, поскольку только они среди всех композиций могут являться минимальными по включению классами в соответствующих энтропийных слоях. Автор предполагает, что на основе свойств регулярных композиций, как описанных в данной работе, так и еще не известных, можно будет впоследствии полностью решить задачу описания области допустимых значений энтропии наследственных классов ориентированных и цветных графов. Следует отметить, что эта глобальная в рамках данной проблематики задача в диссертации решена только частично: установлены лишь некоторые допустимые значения энтропии. Однако структура найденных значений в совокупности с выводом о существовании в указанной области бесконечного множества точек сгущения указывают на существенную разницу по сравнению со значениями энтропии для классов обыкновенных графов и тем самым подчеркивают, насколько эта задача сложна.

Работа носит теоретический характер. Понятийный аппарат и результаты диссертации могут применяться для количественного анализа классов ориентированных и цветных графов и исследования экстремальных задач на графах. Прикладное значение могут иметь предложенные в работе эффективные алгоритмы решения задачи распознавания графов из некоторых специальных классов.

Полученные в работе результаты могут быть использованы при разработке и чтении спецкурсов по теории графов и анализу и разработке алгоритмов.

ЗАКЛЮЧЕНИЕ

.

В данной работе представлены новые результаты, относящиеся к двум направлениям: исследование на основе энтропийного подхода количественных характеристик наследственных классов ориентированных и цветных графов, а также анализ сложности задачи распознавания в минимальных по включению наследственных классах орграфов с наименьшим положительным значением энтропии. Кроме того, проведен сравнительный анализ с ситуацией для наследственных классов обыкновенных графов.