Исследование количественных характеристик наследственных классов ориентированных и цветных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

СОРОЧАН Сергей Владимирович

ИССЛЕДОВАНИЕ КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК НАСЛЕДСТВЕННЫХ КЛАССОВ ОРИЕНТИРОВАННЫХ И ЦВЕТНЫХ ГРАФОВ

01.01.09 — дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород, 2006

Работа выполнена на кафедре математической логики и высшей алгебры факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского

Научный руководитель:

д.ф.-М.н., проф. Алексеев В. Е.

Официальные оппоненты:

д.ф.-м.н., проф. Иорданский М. А. д.т.н., проф. Коган Д. И.

Ведущая организация:

факультет ВМК МГУ им. М. В. Ломоносова

Защита диссертации состоится У сентября 2006 г. в часов на

заседании диссертационного совета Д 212.166.06 при ННГУ им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ им. Н. И. Лобачевского

Автореферат разослан " / " августа 2006 г.

Ученый секретарь диссертационного совета Д 212.166.0i к.ф.-м.н, доцент

Лукьянов В. И.

Общая характеристика работы

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

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

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

1Алексеев В. Е. Наследственные классы и кодирование графов // В сб. Проблемы кибернетики, вып. 39 / Под ред. С. В. Яблонского. — М.: Наука, 1982. — С. 151-164.

2Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // В сб. Проблемы кибернетики, вып. 2 / Под ред. А. А. Ляпунова. — М.: Физматгиз, 1959. — С 75-121.

множество допустимых значений энтропии наследственных классов обыкновенных графов счетно (оно состоит только из чисел вида 1 — доказал существование и дал исчерпывающее описание минимальных по включению классов с заданным значением энтропии3.

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

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

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

Задачи исследования:

•'Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискретная математика. — 1992. — Т. 4, N 2. — С. 148-157.

4 Алексеев В. Е. Об энтропии фрагментно замкнутых классов графов // В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова. — Горький: 11зд-во Горьковского ун-та, 1986. — С. 5-15.

1. Установить существование энтропии наследственных классов ориентированных и цветных графов. Исследовать структуру области допустимых значений энтропии в каждом из этих случаев,'выявить наименьшее положительное значение энтропии и найти все минимальные по включению па-следственные классы в слоях с нулевой и наименьшей ^положительной' энтропией. - ■ • "•• -

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

3. Провести исследование композиций наследственных классов ориентированных и цветных графов. Разработать общий метод для вычисления энтропии композиций. Установить свойства композиций наследственных классов. Описать минимальные по включению классы среди композиций с заданным значением энтропии. Доказать существование и дать характеризацию всех минимальных по включению композиций, содержащих в качестве порожденной заданную композицию. Определить в области значений энтропии наследственных классов ориентированных и цветных графов количество точек сгущения — таких допустимых значений энтропии, которые являются пределами нетривиальных последовательностей других допустимых значений энтропии.

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

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

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

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

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

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

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

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

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

Проведен сравнительный анализ результатов, полученных для наследст-

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

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

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

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

Все результаты второй главы, содержание которой составляют харак-теризация в терминах запрещенных порожденных подграфов большинства наследственных классов орграфов с наименьшей положительной энтропией и определение сложности задачи распознавания в этих классах, получены автором лично. При этом следует отметить, что при обосновании справедливости утверждений теорем 19, 22 и 25 из главы II автором были использованы идеи научного руководителя, позволившие существенно упростить и сократить доказательства указанных теорем. Основная идея и доказательство наиболее важного из результатов главы II о NP-полноте задачи распознавания орграфов из класса транзитивно-двудольных турниров также принадлежат автору.

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

графов бесконечного множества точек сгущения.

Часть результатов главы IV, связанная с обоснованием непредставимости класса ациклических орграфов в виде регулярной композиции никаких других наследственных классов, доказана соискателем лично. Основной результат четвертой главы, устанавливающий минимальность по включению класса ациклических орграфов среди классов с энтропией, равной получен автором совместно с научным руководителем.

Апробация результатов работы. Результаты диссертации докладывались и обсуждались на Молодежных научных школах по дискретной математике п ее приложениям под руководством члена-корреспондента РАН О. Б. Лупаиова (Москва, 1997, 2000), на Международных школах-семинарах "Синтез и сложность управляющих систем" (Нижний Новгород, 1998, 2003, Пенза, 2001), на Международном семинаре "Дискретная математика и ее приложения" (Москва, 2004), на совместных семинарах кафедры математической логики и высшей алгебры факультета ВМК Нижегородского госуни-псрситета, кафедры информатики Нижегородского педагогического университета и отдела дискретной математики НИИ ПМК при ННГУ.

Публикации. По теме диссертации опубликовано 12 работ, список которых приводится в конце автореферата. Среди них 6 статей, опубликованных в Центральной научной печати, а именно: 4 статьи в журнале "Дискретный анализ и исследование операций", одна статья в журнале "Дискретная математика" и одна статья в журнале "Discrete Math. Appl.". Остальные публикации являются тезисами докладов и включены в сборники трудов научных конференций и семинаров. Общее количество страниц статей, опубликованных в Центральной научной печати, составляет 103 страницы. В тезисах докладов на научных конференциях и семинарах опубликовано 26 страниц.

Структура и объем работы. Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения и списка литературы, включающего 57 наименований. Общий объем диссертации составляет 149 страниц машинописного текста, включая 28 иллюстраций. Основные результаты излагаются в главах II, III. Нумерация всех теорем, лемм, следствий и замечаний в диссертации является сквозной, а нумерация формул ведется независимо в пределах каждой главы. Номер каждой формулы состоит из трех позиций, первая из которых указывает на номер главы, вторая — на номер параграфа внутри главы, а третья — на номер формулы внутри параграфа.

Краткое содержание работы

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

В главе I определяются понятия наследственных классов ориентированных и цветных графов, вводится их количественная характеризация — энтропия, доказывается теорема ее существования, устанавливается разрыв-

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

В §1 с помощью леммы о равномерном покрытии5 доказывается, что для любых бесконечных наследственных классов Л" орграфов и У «/-цветных графов существуют пределы - ■ <■'•,■ ■ >

/»<«'(*) = М*) = lim ч. . Л1«1(У) =-Л(У) = lira

п-+оо п(п — 1) ; (")

называемые энтропиями классов X и У соответственно. Здесь ^„(соответственно Уп) — множество всех ориентированных (g-цвбтных) графов из X (из У) с множеством вершин {1,...,п}.

В §2 описаны минимальные по включению классы, имеющие нулевую энтропию.

Пусть 0^(а) = 0(a) — множество всех g-графоп (V, С), у которых C(Vr(2)) = {а}, т.е. каждое ребро имеет цвет а. Такие графы будем называть одноцветными. Очевидно, что h(0(a)) — 0.

Теорема 3. Наследственный класс q-графов бесконечен тогда и только тогда, когда в нем содержится хотя бы один из одноцветных классов О(а), a в {1,...,(/}.

Пусть £ — класс всех пустых орграфов (графов с пустым множеством дуг), С — класс всех полных орграфов (в полном орграфе каждая упорядоченная пара вершин является дугой), Т — класс всех транзитивных турниров (орграфов, в которых каждая пара вершин соединена точно одной дугой и из существования дуг (а, Ь) и (Ь,с) следует существование дуги (о, с)). Эти три класса будем называть простейшими.

Теорема 4. Наследственный класс орграфов бесконечен тогда и только тогда, когда в нем содержится хотя бы один из простерших классов.

В §3 найдено наименьшее положительное значение энтропии наследственных классов ориентированных и цветных графов и описаны минимальные по включению классы в слое с этим значением.

Пусть U и V — непересекающиеся множества. Двудольным орграфом с левой долей U, правой долей V" и множеством дуг Е будем называть тройку (U,V,E), где Е С (U х V) U (V х U). Введем понятие типа Р(х,у)

5Bollobas В., Thomason A. Projections of bodies and hereditarv properties of hvpergraphs // Bulletin of the London Mathematical Society. — 1995. — v. 27. — p. 41?- 12

пары вершин (х,у) 6 UxV по отношению к двудольному орграфу (U,V,E): Р(х,у) = -

а (от слова "absent"), если (х,у) & Е и (у, х) £ Е,

I (от слова "left"), если (х,у) g Е, а (у,х) € Е,

г (от слова "right"), если (х,у) е Е, а (у,х) 0 Е,

d (от слова "double"), если (х, у) б Е и {у,х) 6 Е.

Двудольный орграф может быть задан матрицей, строкам которой поставлены в соответствие вершины левой доли, столбцам — вершины правой доли, а на пересечении строки, соответствующей вершине а, со столбцом, соответствующим вершине Ь, находится тип пары (а, Ь). Эту матрицу будем называть матрицей типов двудольного орграфа. Для непустого множества М С {а,/,г,с£} через В(М) обозначим класс таких двудольных орграфов, у которых все элементы матрицы типов принадлежат М.

Пусть С? = (У,Е) — орграф, а 11\ и {/г — непересекающиеся подмножества множества V. Обозначим через ¿7(1/1,11г) двудольный орграф (С/,, и-2, Е'), где Е' = Е П ((^1 х 1/2) и (1/2 х Щ)).

Пополнением двудольного орграфа В = (Г/, V, Е) назовем любой орграф С — {II и V, Е'), такой, что в(17, V) = В, Е' Э Е.

Пусть Хх и Х2— множества орграфов, а У С {а,/,г,(¿}. Через Х\УХ2 обозначим совокупность всех орграфов б = (У,Е), множество вершин которых можно разбить на две такие части и Рг, что ¿»(И) 6 Л^, с{г2> е Л'-, а со'ьГз) е в(У).

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

Теорема 6. Для наследственного класса орграфов X следующие утверждения равносильны:

(1) Л(Л') > 0;

(2) />(*)> 1/4;

(3) существует такое У С {а, /, г, с1], |У| = 2, что каждый двудольный орграф из В(У) имеет пополнение, принадлежащее X;

(4) существуют такие наследственные классы ориентированных графов Л'ьЛ'а б'{£,С,Т } " "кое г С {а./.г.ф, |У| = 2, что Х1УХ2 С X.

Среди классов вида Х\УХг, фигурирующих в утверждении (4), имеется ровно 30 различных. Это классы, для которых множества X? и У выбираются одним из следующих способов:

Л'ьД'з € {£,С,Т}, а 1' = {а,/} или У^= {<1,1} (число попарно различных классов такого вида равно 18);

(Л'ьЛ'з) -— это любое двухэлементное сочетание с повторениями из множества {£,С,Т}, а У = {а.й} или У = {г,/} (имеется 12 попарно различных классов такого вида).

Далее перейдем к изложению основного результата, характеризующего минимальные по включению наследственные классы д-цветных графов с положительной энтропией.

Пусть V и U — непересекающиеся множества. Двудольным q-графом с долями V и U будем называть тройку (V, U, С), где С : V х U -> Q — {1,...Для множества PCQ обозначим через Б(Р) множество всех таких двудольных ^-графов, у которых C(V х U) С Р.

Пополнением двудольного g-графа G = (V, U, С) назовем любой г/-граф Н = {V U U, С"), такой, чтоотображение С" совпадаете С на множестве VxU. Пополнение, вкотором С'(х,у) = а для всех (х,у) 6 К(2) и С'(х,у) = 13 для всех (х,у) е i/'2\ обозначим через G[a,[i\. Для множества PC.Q и цветов a,0 £Q определим множество В(Р, а, (3) = {G[a,(3] : G Е 23(Р)}.

Пусть X -— класс g-графов. Обозначим через С{Х) множество всех двудольных g-графов, имеющих пополнения, принадлежащие X.

Основной результат, характеризующий минимальные по включению наследственные классы q-цвётных графов с положительной энтропией, аналогичен результату для наследственных классов орграфов.

' Теорема 7. Пусть X — наследственный класс q-графов. Следующие утверждения равносильны:

(1) Л(*)>0;

(2) h(X) > | log? 2;

(3) существует такое множество Р С Q, |Р| = 2, что В(Р) С С(Л');

(4) существует такое множество Р С Q, \Р\ = 2 и такие «, 3 6 Q, что В(Р,а,0) С X.

Следствие 3. Существует \q2(q2 — 1) минимальных наследственных классов q-графов с энтропией, равной | loge 2. Ими являются в точности все классы вида В(Р,а,0), где а,/3 е Q, a Р С Q, |Р| = 2.

Анализируя результаты, полученные в теоремах 6 и 7, можно сделать важный вывод, касающийся значений энтропии, которые могут принимать наследственные классы орграфов и д-графов. ,

Следствие 4. Множества значений энтропии наследственных классон ориентированных и q-цвётных графов являются разрывными. Именно, если X и У — бесконечные наследственные классы орграфов и q-графов соответственно, то h(X) — 0 или 1/4 < h(X) < 1, Л(>') = 0 или (1/2) log4 2 < h(y) < 1.

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

На основе полученного описания минимальных по включению наследственных классов ориентированных и цветных графов возникает потребность в более пристальном изучении наследственных классов двудольных графов указанных типов. С этой целью в §4 вводятся понятия двудольных энтропий наследственных классов двудольных ориентированных и" цветных графов, доказывается теорема их существования и полностью описываются области их допустимых значений.

Пусть У Ii) = У — наследственный класс двудольных д-графов. Обозначим через Ущ.па множество двудольных g-графов из У, у которых V = {1,2,..., тг 1}, U = {«1 + l,ni + 2,.., «1 Доказано существование

двойного предела

hß(y)= lim 1ое.1У"..п,|

щ-+оо ЩПо

>12—ЮО i-l'-i

называемого двудольной энтропией класса у. Справедлива

Теорема 9. Двудольная энтропия hß(y) любого бесконечного класса У двудольных (/-цветных графов принимает только значения из множества {О = log, 1, log, 2, log,(«-I), log, 9=1}.

Существование энтропий h(X) и hß (У) класса д-графов и класса У двудольных д-графов используется далее в главе III при исследовании композиций наследственных классов д-графов.

Для наследственных классов двудольных орграфов справедлив аналогичный результат.

Теорема 10. Двудольная энтропия

ПВ(У)= lim

712 —ЮО 1

бесконечного наследственного класса У двудольных орграфов существует и принимает значения из множества 1 = 0, к^ 2 = 1/2, 3 =

(1/2)10(5,3, 1ой,4=1}.

Результаты главы I опубликованы в работах [1, 2, 3, 4, 12].

Глава II нацелена па решение вопросов алгоритмической сложности. Здесь рассматривается задача распознавания принадлежности заданного графа определенному классу. В качестве классов, на которых проводится исследование задачи распознавания, выбраны описанные в главе I минимальные по включению наследственные классы орграфов среди классов с наименьшим положительным значением энтропии. Большая часть результатов, относящихся к сложности распознавания, является следствием решения задачи характсризацни этих классов в терминах запрещенных порожденных подграфов. Такую характеризацию удалось дать для всех выше упомянутых классов, кроме двух, для которых были найдены другие подходы к решению проблемы распознавания. Установлено, что в каждом минимальном наследственном классе орграфов с наименьшей положительной энтропией, за исключением одного, задача распознавания разрешима за полиномиальное время. С другой стороны, выявлен класс, отличающийся от всех остальных, в котором задача распознавания МР-полна. Тем самым получена исчерпывающая классификация указанных минимальных классов по сложности решения задачи распознавания.

В §1 для наследственного класса орграфов вводятся понятия дополнения и обращения и устанавливается взаимосвязь между решениями задач

характеризации этих классов. Показано, что множество из 30-ти минимальных по включению наследственных классов орграфов с энтропией, рапной 1/4, разбивается на 14 классов эквивалентности, в каждом из которых любой класс является либо дополнением, либо обращением некоторого другого класса.

Поэтому достаточно решить задачи характеризации и распознавания только для таких из тридцати классов, перечисленных в главе I, ни одни из которых не является дополнением и обращением другого. Эти задачи решаются для классов вида Л^УАг, для которых множества A'i, Х> и У выбираются одним из следующих способов:

Xi = Х2 — £, a У = {a,if}, или У — {a,d}, или У = {/,/•}, или Y — {<1,/} (4 класса);

Х\ = £, Хг = С, а Y — {а,/}, или Y = {a,d}, или 1' = {/,г} (3 класса);

Х\ — £, Х2 = Т, а Y = {a, I}, или Y = {я, d}, или Y = {I, ?■}, или Y — (4 класса);

Xi = Х2 = Т, а У = {а,/}, или У = {а, с?}, или 1" = {i,r} (3 класса).

В §§2-6 проводится исследование задач характеризации и распознавания для каждого из указанных классов, за исключением класса ТIrT. В >¡2 это делается для классов, взаимно однозначно соответствующих классам обыкновенных двудольных и расщепляемых графов, в §§3 и 4 -— для оставшихся классов вида £Y£ и £УС (|У| = 2) соответственно, а в !|§5 и G длп классов £УТ и двух классов вида ТУТ (|У| = 2) соответственно. Установлено, что задача распознавания орграфов из всех классов, кроме ThТ, разрешима за полиномиальное время.

В §7 проводится исследование последнего оставшегося класса Т/гТ, названного классом транзитивно-двудольных турниров. Длп определения сложности задачи распознавания орграфов из этого класса была рассмотрена следующая вспомогательная задача, называемая задачей о (;;,г)-раскраскс гиперграфа. Дан г-однородный гиперграф F = (V'(F), E(F)), т.е. гиперграф, в котором каждое гиперребро е е E(F) является одним из г-элементных подмножеств множества V(F). Требуется ответить па вопрос, существует ли такое множество U С V(F), что п любом гипсррсбро е 6 E{F) имеется в точности р вершин, принадлежащих множеству U, т.е. \U П е| = р.

Известно6, что задача о (р,г)-раскраске гиперграфа является ХР-полной при всех г > 3 и таких р, что 1 < р < г. Используем этот результат при р — 2, г = 4. Справедлива следующая

Теорема 26. Задача о (2,4)-раскрасие гиперграфа полиномиально сводится к задаче распознавания орграфов из класса TlrT.

Следует отметить, что доказательство теоремы 26 представляет собой модификацию на случай орграфов доказательства NP-пол ноты зада-

6Schaefer Т. J., The complexity of satisfiability problems, I'roc. 10th Ann. ACM Syirip. on Theory of Computing, Assoc. for Computing Machinery, New York. — 1078. -- 216 "J'Mi.

чи распознавания неориентированных графов из аддитивных порожденно-наследственпых классов7.

Следствие 6. Задача распознавания орграфов из класса транзнтивно-дпудольных турниров является NP-полной.

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

Результаты главы II опубликованы в работах [9, 10, 11].

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

При описании области допустимых значений энтропии наследственных классов обыкновенных графов9,10 определяющую роль играют классы £jj всех графов, в каждом из которых множество вершин можно разбить на i + j секций, среди которых i секций порождают полные, a j секций — пустые подграфы, i,j € Z+. Оказалось, что классы £ ¡j, где i + j = k, являются минимальными (по включению) среди наследственных классов обыкновенных графов с энтропией h = 1 — 1 /к, к 6 Z+, причем допустимые значения энтропии исчерпываются только числами указанного вида.

Целью третьей главы является исследование специальных фрагментно замкнутых классов, называемых в дальнейшем композициями наследственных классов цветных графов, которые являются обобщением на случай q цветов классов для произвольных целых неотрицательных i и j.

В §1 вводится понятие композиции наследственных классов g-графов и показывается, что проблема нахождения их энтропии сводится к некоторой задаче квадратичного программирования с линейными ограничениями.

Пусть для каждой пары i,j, где 1 < i,j < k, i < j и к > 2, при i = j выбран некоторый бесконечный наследственный класс X" q-графов, а при i ^ j—некоторый бесконечный наследственный класс X** двудольных q-графов. Полагаем Л'-'' = X'J при любых i < j. Множество всех выбранных

'Farrugia Л.. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard //Electron. J. Combin. — 2004. — V. 11(1) # 46. 9 p.

®Кмеличев В. А., Мельников О. II., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. Москва: Пач ка, гл. ред. физ.-мат. лит., 1990.

51 Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискретная математика. М. — 1D92. — Т. 4, вып. 2. — С. 148-157.

"'Алексеев В. Е. Исследование количественных и сложностных характеристик наследственных классов графов. Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.01.09 — математическая кибернетика. Ниж-ниГ| Новгород. 2002.

классов обозначим через Х^кК Тогда к-композицией С(Х^) —

наследственных классов д-графов из А''*' назовем совокупность таких </графов С, что множество вершин в й можно разбить на непересекающиеся подмножества VI,...,14 (некоторые из них могут быть пустыми) так, что € при всех » ф з, %,з = Классы

Хп,...,Хкк будем называть секциями ¿-композиции С(ЛМ*">).

Каждой ¿-композиции С(ХО) поставим в соответствие симметрическую квадратную матрицу Я(*) = Н = {№) порядка к, в которой Л" = Н(Х"), а Л'-* = г,3 = Матрицу Н(к) назовем

матрицей энтропий ¿-композиции

Заметим, что композиция определена с точностью до нумерации секций. Поэтому матрица энтропий определяется с точностью до одновременных перестановок строк и столбцов.

Рассмотрим проблему вычисления энтропии введенных ¿-композиций. Справедлива следующая

Теорема 27.

Л (с(ХМ)) = тах | К^х^ ^ х5 = 1, х} > 0, 3 = 1,..., к 1.

Таким образом, проблема вычисления энтропии любой композиции наследственных классов цветных графов сводится к задаче поиска максимума квадратичной формы с линейными ограничениями.

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

Перепишем полученную в теореме 27 задачу математического программирования в матричной форме: найти

тах{^(х) =хтЯх | 1тх = 1, х>0}. (I)

Здесь х = {л?1,... ,аг*}т, 1 = {1,..., О = {0,... ,0}^, Я — матрица энтропий ¿-композиции С(Х^), а запись х>0 означает, что каждая компонента вектора х неотрицательна.

Композицию С(Д^*') назовем регулярной к-композицией, если для ее матрицы энтропий Я выполнены

(1) требование максимальности: С}1Н С? <0 (Я - матрица размера к х (Л: — 1), п столбцах которой записаны базисные векторы подпространства решений уравнения 1тх = 0) и

(2) условие внутренней допустимости: Н~1Х > 0 (неравенство понимается покомпонентно). .

Решение задачи (I), а следовательно, и проблемы вычисления композиций. доставляет

Теорема 28. Энтропия каждой регулярной к-композиции наследственных классов (¡-графов вычисляется по формуле

Ь (СЧЛ^*')) = 1/1тЯ-11 = АсШ / Ач

Г ¡,^=1

(здесь Лу алгебраическое дополнение к элементу Л4'), причем у соответствующей задачи (I) квадратичного программирования имеется единственная точка максимума х° = Н~11 /1т//_ 11, лежащая внутри допустимой обмети Т> = {х 6 II*' | 1тх = 1, х > 0} этой задачи.

Любая нерегулярная ком позиция не является минимальным (по включению) классом среди наследственных классов (¡-графов с заданным значением энтропии; энтропия нерегулярной композиции равна максимальной энтропии целиком содержащейся в ней композиции с меньшим количеством секций, причем у соответствующей задачи (I) квадратичного программирования существует точка максимума, лежащая на границе допустимой области Г> этой задачи.

Теорема 28 является основным результатом главы.

Поскольку проблема вычисления энтропии наследственных классов цветных графов успешно решается для композиций таких классов, а осо-бос значение при этом играют регулярные композиции, представляется интересным изучить основные свойства последних. В §3 устанавливаются следующие свойства регулярных композиций: во-первых, находится связь между энтропилми регулярных композиций, одна из которых порождается удалением некоторой секции другой; во-вторых, обнаруживается, с одной стороны, наследование свойства регулярности хотя бы одной порожденной А'-композицисй регулярной (к + 1)-композиции, а, с другой стороны, приводится пример регулярной композиции, не все порожденные композиции которой регулярны.

^-композитно СДЛ'1*+1)), полученную из (А;+1)-композишш С(Л"(А;+1)) удалением /-и секции, назовем порожденной композицией, г = 1, ...,&+■ 1.

В теореме 29 найдена взаимосвязь между порожденной и порождающей композициями. Установлено, что если + 1)-композиция и

¿•-композиция = С(."?(А)) являются регулярными, то их эн-

тропии связаны соотношением

1 _ 1 _ (1тЯ-'Ь-1)2

h(C(XV+V))~ h(c{XW)) bJH-^b-h '

где Н —■ матрица энтропий композиции С(Х^), h = h(Xk+ltk+t), h — fc-мерный вектор-столбец, такой, что №,к+1 — Ьв(Х->^'+1), j = 1 1 = il.....

В теореме 30 доказано наследование свойства регулярности хотя бы одной порожденной fc-композицией регулярной (к + 1)-композиции, причем установлена регулярность порожденной fc-композиции с наибольшим значением энтропии.

С другой стороны, при любом q > 4 найден пример регулярной 3-композиции, содержащей нерегулярную 2-композицию.

В §4 определяются нижняя и верхняя оценки значения энтропии произвольной регулярной композиции наследственных классов g-графоп в зависимости от энтропий ее порождающих классов однодольных и двудольных д-графов.

Теорема 31. Пусть С(Х^) —регулярная к-композицип наследственных классов q-графов из Х1кК Тогда ее энтропия удовлетворяет неравенствам

тах^Л(ДГ") < h (c(Xik>)} < maxЛВ(ЛГ''■'").

В §5 вводится понятие правильной композиции наследственных классов и доказывается, что каждая регулярная правильная композиция является минимальным по включению классом среди композиций с заданным значением энтропии.

Для произвольного непустого множества М С Q обозначим через 0<?>(М) = О(М) класс таких g-графов G = (F,C), что С(1',2)) С А/. Аналогично для непустого множества Р С Q обозначим через В^'ЦР) = В(Р) множество таких двудольных g-графов, для которых C(V х U) С Р. Нетрудно видеть, что h(0(M)) = log, |Л/|, a hB(B(P)) - log,, |Р|.

Композицию С(ЛМ*)) = \\Х'1назовем правильной к-композицией, если ХМ = O(Mjj), X*i ~ B(Mij) при некоторых непустых Mjj С Q, Mi,- С (J, г ф j, i, j = 1,...,к. Справедлива следующая

Теорема 32. При всех натуральных к >2 каждая правильная регулярная k-композиция наследственных классов q-графов является минимальным элементом в множестве k-композиций с соответствующим значением энтропии.

В §6 проводится исследование (к + 1)-композиций, порождающих заданную регулярную ¿-композицию: здесь, во-первых, получены необходимые

и достаточные условия для регулярности (к + 1)-композиций, содержащих заданную регулярную ¿¡-композицию; во-вторых, установлено существование и приведена характеризация минимальных по включению среди таких композиций; в-третьих, доказано, что любая регулярная ¿¡-композиция порождается удалением одной из секций некоторой регулярной (к + 1)-композицни; наконец, в-четвертых, установлена континуальность множества наследственных классов цветных графов с нулевой и ненулевой энтропией.

Следующая теорема представляет собой критерий регулярности (к +1)-композиции, содержащей заданную регулярную Аг-композицию.

Теорема 33. Пусть II — матрица энтропии регулярной к-композиции

наследственных классов д-графов из а С(Д;(Л+1))—(&+1)-

композицип, порождающая С(Х^). Тогда для того, чтобы С(А'";+1)) являлась регулярной, необходимо и достаточно выполнение неравенств

1тЯ-1Ь-1>0, ЬтЯ-1Ь-/1>0, (1гтЯ-,11 — /г) Н~11 — (1ТЯ-1Ь — 1) Я-1Ь > О.

На основе теоремы 33 устанавливается еще одно важное свойство регулярных композиций. Справедлива

Теорема 34. Любая регулярная к-композиция наследственных классов (¡-графов порождается удалением одной секции из некоторой регулярной (к + 1 )-композпцин.

Из теоремы 34 вытекает

Следствие 16. Регулярные к-композиции наследственных классов д-графов существуют при всех <7 > 2, к > 2. Число регулярных композиций счетно.

Возникает вопрос, как много существует наследственных'классов цвет-пых графов с нулевой и ненулевой энтропией. Ответ на этот вопрос доставляет

Теорема 35. Множество фрагментно замкнутых классов д-графов с нулевой энтропией континуально. Кроме того, если Я — матрица энтропий регулярной к-композиции, то имеется континуальное семейство наследственных классов д-графов с энтропией, равной 1 /1ТЯ~' 1.

В трех следующих ниже утверждениях устанавливается существование н приводится характеризация минимальных по включению регулярных (к + 1)-композиций, целиком содержащих заданную регулярную к-

комПОЗИЦИЮ.

Теорема 36. Регулярные (к +- 1)-композиции с наименьшим возможным значением энтропии, целиком содержащие заданную регулярную к-

композицию, существуют. Кроме того, если Я =

Я ь

и' л

— матрица

энтропий регулярной (к + 1)-колнтознции С(А'*+1'), порождающей регулярную композицию С(Х(к)) с матрицей энтропий Н, то для того, чтобы

С(*(*+1>) имела наименьшую возможную энтропию среди всех композиций, порождающих С(Х^), необходимо, чтобы Л = 0.

Следствие 17. Если Я —

Я

0

— матрица энтропий регулпр-

ной композиции С(Хок+1^), имеющей наименьшую возможную энтропию среди всех (к + 1)-композиций, порождающих регулярную к-композицию С[Х^), то вектор Ь° удовлетворяет условиям Ь° 6 72,, где

П = {Ъ | (к^Н^Ь - Л) Н~х1 - (1ТЯ"1Ь - 1) Я"1!! > О,

1тН-1Ъ-1>0, € 2.log, -!),!}, , = 1,...,Дг>

шш-:--г тт 11--

Теорема 37. Пусть Я =

я

0

(1тЯ-'Ь°-1)2 (Ь°)ТЯ-1Ь° •

— матрица энтропий ре-

гулярной композиции С(Л'о*+1'), имеющей наименьшую возморкную энтропию среди всех (к + 1 )-иомпозиций, порождающих регулярную к-композицию С(Х(к)). Тогда при любом векторе Ь высоты к с компонентами из множества {logq2,log93,...,^ogll(g — 1),1} если Ь < Ь°, Ь ф Ь°,

то (к + 1)-композиция С(Л,'А,+1>) с матрицей энтропий Я =

я ь

ь1 0

не является регулярной, т.е. Ь ^ 7?..

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

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

Теорема 38. Пусть — регулярная (А: + 1)-композиция на-

следственных классов ^-графов, (к + 1)-я секция которой сама является регулярной тп-композицией наследственных классов: А'*+М + 1 = СО,<"1)). Тогда класс д-графов С((ЛМ*+1,\{.¥':+1'*+1})и>?(т)) является регулярной (к + т)-композицией, имеющей энтропию, равную энтропии композиции С7(*<*+1>).

В заключительном §8 главы III вводятся понятия монотонно возрастающей последовательности наследственных классов g-графов, минимальной верхней границы и точки сгущения энтропии. При помощи аппарата сложных композиций и свойств регулярных композиций, доказанных в предыдущих параграфах, устанавливается, что в области допустимых значений энтропии фрагментио замкнутых классов ^-графов при q > 2 существует бесконечное множество точек сгущения.

' оо

Фрагмснтно замкнутый класс X" = (jj Х^ назовем минимальной верх-

fc=i

ней границей последовательности : к £ N} бесконечных наследст-

венных классов д-графов.

Будем говорить, что последовательность {<¥'*' : к € N} монотонно возрастает, если .V'1» С .¥<2) С ... С Л^'-1» С «¥<*> С С ...

Монотонно возрастающую последовательность {Л"'*' : к 6 N} назовем нетривиальной, если ¿(.V'1') < h{X™) < ... < h(X^) <...< h(X').

Поскольку последовательность значений энтропий классов нетривиальной монотонно возрастающей последовательности монотонно не убывает и ограничена сверху, она сходится. Значение h* = h(X*) энтропии нетривиальной минимальной верхней границы X* назовем точкой сгущения, если оно совпадает с пределом последовательности h(X^) при к —> оо:

h(.V*) = lim Л(Л'<*>).

k-ix

Лемма 11. При 2 < |Л/| = m < q каждый из классов О(М) является нетривиальной минимальной верхней границей; соответственно каждое из значении вида log9 tri, m = 2 ,...,q является точкой сгущения энтропии.

Опираясь на лемму 11 и используя аппарат сложных композиций, описанный в §7, при всех q > 2 удалось определить количество точек сгущения в области значений энтропии наследственных классов q-графов. Ответ на поставленный вопрос дает

Теорема 39. В области допустимых значений энтропии фрагментио замкнутых классов q-графов при q > 2 существует бесконечное множество точек сгущения.

Полученный результат существенно отличается от ситуации при q = 2.

Результаты главы III опубликованы в работах [5, 6, 7, 8].

Все результаты, полученные в главе III, в полной мере переносятся и на композиции наследственных классов орграфов. В главе IV установлено существование таких наследственных классов орграфов с положительной энтропией, которые, с одной стороны, являются минимальными по включению в своем энтропийном слое, но, с другой стороны, не представляются в виде регулярной композиции никаких других наследственных классов. Установлено, что к этим классам относится класс Л всех ациклических орграфов, т.е. орграфов, не содержащих ориентированных циклов (в том числе и двусторонней дуги) в качестве порожденных подграфов. Легко ви-

деть, ЧТО Л(Д) = ,

Теорема 40. Класс А ациклических орграфов не представляется в виде регулярной композиции никаких наследственных классов орграфов.

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

Теорема 41. Для любого ациклического орграфа Б существует такой неориентированный граф С(£>), что в каждом-орграфе (£>)), полученном из С(/3) в результате произвольной ациклической ориентации его ребер, найдется порожденный подграф, изоморфный Р.

Из теоремы 41 следует

Теорема 42. Энтропия Н{Х) любого наследственного класса X, целиком содержащегося в классе А ациклических орграфов в качестве собственного подмножества, строго меньше

Следствие 18. Класс А ациклических орграфов является минимальным по включению среди всех наследственных классов орграфов с энтропией, равной ~.

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

Публикации по теме диссертации

1. Алексеев В. Е., Сорочан С. В. Об энтропии наследственных классов ориентированных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики. — 2000. — Т. 7, N 4. — С. 20-28.

2. Алексеев В. Е., Сорочан С. В. Об энтропии наследственных классов цветных графов // Дискретная математика. М. — 2000. — Т. 12, вып. 2. — С. 99-102.

3. Сорочан С. В. Об энтропии фрагментно замкнутых классов ориентированных графов // Материалы первой молодежной научной школы по дискретной математике и ее приложениям (Москва, 1997 г.). - М.: Изд-во механико-математического факультета МГУ, 1997.

4. Сорочан С. В. Об энтропии фрагментно замкнутых классов цветных графов // Материалы XII Международной школы-семинара "Синтез

и сложность управляющих систем" (Нижний Новгород, 1998 г.). ......

Нижний Новгород.: Издательство Нижегородского государственного педагогического университета, 1998.

5. Сорочан С. В. Область значений энтропии секционных классов цветных графов // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 сентября 2000 г.). — М.: Изд-во механико-математического факультета МГУ, 2000. — С. 81-86.

6. Сорочан С. В. Лемма о равномерном покрытии и многодольная энтропия наследственных классов многодольных цветных графов // Материалы XII Международной школы-семинара "Синтез и сложность управляющих систем" (Пенза, 15-21 октября 2001 г.) Часть II. М.: Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2001. — С. 205-212.

7. Сорочан С. В. Об энтропии композиций наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики, 2002. — Т. 9, N 1.

— С. 59-83.

8. Сорочан С. В. О регулярных композициях наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики, 2003. — Т. 10, N 1. — С. 79-104.

9. Сорочан С. В. Характеризация и распознавание ориентированных графов из наследственных классов с наименьшим положительным значением энтропии // Материалы IV Международной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 27 октября — 1 ноября 2003 г.). Нижний Новгород.: Издательство Нижегородского государственного педагогического университета,.2003. — С. 73-75.

10. Сорочан С. В. Алгоритмические и сложностные вопросы распознавания орграфов из наследственных классов с наименьшим положительным значением энтропии // Материалы Восьмого Международного семинара "Дискретная математика и ее приложения" (Москва, 2-6 февраля 2004 г.). М.: Издательство механико-математического факультета МГУ, 2004. — С. 365-367.

11. Сорочан С. В. Характеризация и распознавание орграфов из наследственных классов с наименьшим положительным значением энтропии // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики, 2005. — Т. 12, N 2. — С. 12-55.

12. Alekseev V. Е., Sorochan S.'V., On the entropy of hereditary classes of colored graphs // (Russian) translation in Discrete Math. Appl. — 2000.

— 10, no. 3. — 273-277.

Подписано в печать 03.07.2006. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Зак. 1064. Тир. 100.

Типография Нижегородского госуниверситета. Лиц. ПД № 18-0099 от 04.05.2001. 603000, Н. Новгород, ул. Б. Покровская, 37.

ВВЕДЕНИЕ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

I. ОБ ЭНТРОПИИ НАСЛЕДСТВЕННЫХ КЛАССОВ ОРИЕНТИРОВАННЫХ И ЦВЕТНЫХ ГРАФОВ. МИНИМАЛЬНЫЕ ПО ВКЛЮЧЕНИЮ КЛАССЫ В СЛОЯХ С НУЛЕВОЙ И НАИМЕНЬШЕЙ ПОЛОЖИТЕЛЬНОЙ ЭНТРОПИЕЙ

Основные понятия главы I

1. Лемма о равномерном покрытии и существование энтропии наследственных классов ориентированных и цветных графов

2. Минимальные по включению наследственные классы ориентированных и цветных графов, имеющие нулевую энтропию

3. Наименьшее положительное значение энтропии наследственных классов ориентированных и цветных графов. Описание минимальных по включению классов в слое с этим значением

3.1. Двудольные орграфы, их матрицы и свойства

3.2. Наименьшее положительное значение энтропии наследственных классов орграфов. Минимальные по включению классы в слое с этим значением

3.3. Двудольные цветные графы

3.4. Наименьшее положительное значение энтропии наследственных классов цветных графов. Минимальные по включению классы в слое с этим значением

3.5. Разрывность множеств значений энтропии наследственных классов ориентированных и цветных графов 3G

4. Двудольная энтропия наследственных классов двудольных цветных и ориентированных графов

Выводы к главе I

II. ХАРАКТЕРИЗАЦИЯ И РАСПОЗНАВАНИЕ ОРГРАФОВ ИЗ НАСЛЕДСТВЕННЫХ КЛАССОВ С НАИМЕНЬШИМ ПОЛОЖИТЕЛЬНЫМ ЗНАЧЕНИЕМ ЭНТРОПИИ

Основные понятия и содержание главы II

1. О связи характеризации наследственного класса орграфов с характеризацией его дополнения и обращения

2. Характеризация классов, взаимно однозначно соответствующих классам двудольных и расщепляемых графов

3. Характеризация классов с пустыми долями

3.1. Класс SalS

3.2. Класс SlrS

3.3. Класс SdlS

4. Характеризация классов с пустой и полной долями

• 4.1. Класс £а1С

4.2. Класс Sir С

5. Характеризация классов с пустой долей и долей, вершины которой порождают транзитивный турнир

5.1. Класс SadT

5.2. Класс SalT

5.3. Класс EdlT

5.4. Класс SWT

6. Характеризация двух классов транзитивно-двудольных ор-Щ графов. Полиномиальная разрешимость задачи распознавания в тринадцати классах

6.1. Класс TadT

6.2. Сложность распознавания орграфов в двенадцати классах

6.3. Класс TalT

7. Класс TlrT

7.1. Специальные транзитивно-двудольные турниры и их свойства

7.2. NP-полнота задачи распознавания орграфов из класса транзитивно-двудольных турниров

Выводы к главе II

Ш III. ОБ ЭНТРОПИИ КОМПОЗИЦИЙ НАСЛЕДСТВЕННЫХ КЛАС

СОВ ЦВЕТНЫХ ГРАФОВ

Основные понятия и содер?кание главы III

1. Композиции наследственных классов цветных графов и проблема вычисления их энтропии

1.1. Понятие композиции наследственных классов цветных графов

1.2. Проблема вычисления энтропии композиций

2. Значения энтропии композиций наследственных классов щ 2.1. Анализ задачи квадратичного программирования, полученной в

§

2.2. Вспомогательные задачи квадратичного программирования и соответствие между ними

2.3. Исследование задач (I), (II) и (III)

2.4. Регулярные и нерегулярные композиции наследственных классов цветных графов. Вычисление их энтропии

2.5. Основные замечания и следствия из теоремы об энтропии композиций

3. Важнейшие свойства регулярных композиций

3.1. Взаимосвязь между порожденной и порождающей композициями

3.2. Наследование свойства регулярности и следствия из него

3.3. Существование нерегулярных порожденных композиций у некоторых регулярных порождающих композиций

4. Нижняя и верхняя оценки энтропии регулярных композиций

5. О минимальных по включению композициях наследственных классов цветных графов

6. О минимальных по включению регулярных (к + ^-композициях, содержащих заданную регулярную ^-композицию

6.1. Критерий регулярности порождающей композиции и следствия из него

6.2. Существование и другие свойства регулярных композиций

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

7. О сложных композициях наследственных классов

8. Минимальные верхние границы и точки сгущения энтропии наследственных классов цветных графов

Выводы к главе III

IV. О МИНИМАЛЬНЫХ ПО ВКЛЮЧЕНИЮ НАСЛЕДСТВЕННЫХ КЛАССАХ ОРГРАФОВ С ПОЛОЖИТЕЛЬНОЙ ЭНТРОПИЕЙ, НЕ ЯВЛЯЮЩИХСЯ РЕГУЛЯРНЫМИ КОМПОЗИЦИЯМИ ДРУГИХ

НАСЛЕДСТВЕННЫХ КЛАССОВ

Содержание главы IV

1. Класс ациклических орграфов и регулярные композиции орграфов

2. Основной результат главы IV

2.1. Универсальные графы ациклических орграфов

2.2. Минимальность класса ациклических орграфов

Вывод к главе IV

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

При решении задачи количественного перечисления [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, открывают обширную область для дальнейших исследований, направленных на более глубокий анализ композиций наследственных классов. При этом наиболее перспективным видится изучение именно регулярных композиций, поскольку только они среди всех композиций могут являться минимальными по включению классами в соответствующих энтропийных слоях. Автор предполагает, что на основе свойств регулярных композиций, как описанных в данной работе, так и еще не известных, можно будет впоследствии полностью решить задачу описания области допустимых значений энтропии наследственных классов ориентированных и цветных графов. Следует отметить, что эта глобальная в рамках данной проблематики задача в диссертации решена только частично: установлены лишь некоторые допустимые значения энтропии. Однако структура найденных значений в совокупности с выводом о существовании в указанной области бесконечного множества точек сгущения указывают на существенную разницу по сравнению со значениями энтропии для классов обыкновенных графов и тем самым подчеркивают, насколько эта задача сложна.

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

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

ЗАКЛЮЧЕНИЕ

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

1. Алексеев В. Е. О сжимаемых графах // В сб. Проблемы кибернетики, вып. 36 / Под ред. С. В. Яблонского. — М.: Наука, 1979. — С. 23-32.

2. Алексеев В. Е. Наследственные классы и кодирование графов //В сб. Проблемы кибернетики, вып. 39 / Под ред. С. В. Яблонского. — М.: Наука, 1982. — С. 151-164.

3. Алексеев В. Е. О влиянии локальных ограничений на определение числа независимости графа // В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1982. — С. 3-13.

4. Алексеев В. Е. Об энтропии фрагментно замкнутых классов графов // В сб. Комбинаторно-алгебраические методы в прикладной математике / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1986. — С. 5-15.

5. Алексеев В. Е. Об энтропии двумерных фрагментно замкнутых языков // В сб. Комбинаторно-алгебраические методы и их применения / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1987. — С. 5-13.

6. Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискретная математика. М. — 1992. — Т. 4, вып. 2. — С. 148-157.

7. Алексеев В. Е. О нижних ярусах решетки наследственных классов графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики. — 1997. — Т. 4, N 1. — С. 3-12.

8. Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики. — 1999. — Т. 6, N 4. — С. 3-19.

9. Алексеев В. Е., Коробицын Д. В. О сложности некоторых задач на наследственных классов графов // Дискретная математика. М. — 1992. Т. 4, N 4. — С. 34-40.

10. Алексеев В. Е., Сорочан С. В. Об энтропии наследственных классов ориентированных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики. — 2000. — Т. 7, N 4. — С. 20-28.

11. Алексеев В. Е., Сорочан С. В. Об энтропии наследственных классов л. цветных графов // Дискретная математика. М. — 2000. — Т. 12,вып. 2. — С. 99-102.

12. Алексеев В. Е., Таланов В. А. Графы. Модели. Алгоритмы: Учебник.

13. Нижний Новгород: Изд-во ННГУ, 2005.

14. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М: Мир, 1979.

15. Гантмахер Ф. Р. Теория матриц. — М.: Гостехиздат, 1953.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М: Мир, 1982.

17. Емеличев В. А., Мельников 0. И., Сарванов В. И., Тышкевич Р. И. ^ Лекции по теории графов. Москва: Наука, гл. ред. физ.-мат. лит.,1990.

18. Зыков А. А. Основы теории графов. — М.: Наука, 1987.

19. Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука, 1984.

20. Калихман И. Л. Сборник задач по математическому программированию. — М.: Высшая школа, 1975.

21. Карманов В. Г. Математическое программирование. — М.: Наука, 1975.

22. Коробицын Д. В. О сложности определения числа доминирования в моногенных классах графов // Дискретная математика. М. — 1990.1. Т. 2, вып. 2. — С. 90-97.

23. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.

24. Сорочан С. В. Об энтропии фрагментно замкнутых классов ориентированных графов // Материалы первой молодежной научной школы по дискретной математике и ее приложениям (Москва,1997 г.). — М.: Изд-во механико-математического факультета МГУ, 1997.

25. Сорочан С. В. Об энтропии композиций наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики, 2002.1. Т. 9, N 1. — С. 59-83.

26. Сорочан С. В. О регулярных композициях наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. Новосибирск: Издательство Института математики, 2003.1. Т. 10, N 1. — С. 79-104.

27. Харари Ф. Теория графов. — М.: Мир, 1973.

28. Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.

29. Ху Т. Ч., Шинг М. Т. Комбинаторные алгоритмы / Перевод с английского — Нижний Новгород: Изд-во Ншкегородского госуниверситета им. Н.И. Лобачевского, 2004.

30. Чандрасекхаран К. Введение в аналитическую теорию чисел. — М.: Мир, 1974.

31. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976.

32. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // В сб. Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. — С 75-121.

33. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.

34. Alekseev V. Е. On the entropy values of hereditary classes of graphs // Discrete Mathematics and Applications. — 1993. — V 3, N 2. — P. 191-199.^

35. Alekseev V. Е. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. — 2004. — 132. — 17-26.

36. Alekseev V. E. Polynomial algorithm for finding the largest independent sets in graphs without forks // Discrete Applied Mathematics. — 2004. — 135. — 3-16.

37. Alekseev V. E., Sorochan S. V., On the entropy of hereditary classes of colored graphs // (Russian) translation in Discrete Math. Appl. — 2000. — 10, no. 3. — 273-277.

38. Balas E., Yu Ch. S. On graphs with polynomially solvable maximum weight clique problem // Networks. — V. 19. — 1989. — 247-253.

39. Bollobas B. Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring // Proceedings of the International Congress of the Mathematicians, Berlin, 1988, Aug. 18-27, v. III. — p. 333-341.

40. Bollobas В., Thomason A. Projections of bodies and hereditary properties of hypergraphs // Bulletin of the London Mathematical Society. — 1995. — v. 27. — p. 417-424.

41. Erdos P., Simonovits M. A limit theorem in graph theory // Stud. Sci. Math. Hungar. — 1966. — V. 1. — P. 51-57.

42. Farrugia A., Vertex-partitioning into fixed additive induced-hereditaryproperties is NP-hard // Electron. J. Combin. — 2004. — V. 11(1) # 46. 9 p.

43. Golumbic M. Ch. Algorithmic graph Theory and perfect graphs. — N.Y.: Academic Press, 1980.

44. Grotschel M., Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs // Annals of Discrete Mathematics. — 1984. — V. 21. — P. 325-356.

45. Grotschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimization. — Springer Verlag. 1994.л 52. Hertz A. Polynomially solvable classes for the maximum stable setproblem // Discrete Appl. Math. — 1995. — V. 60. — P. 195-210.

46. Lovasz L., Plummer M. D. Matching theory. — Amsterdam: North-Holland, 1986.

47. Mosca R. Polynomial algorithms for the maximum stable set problem on particular classes of iVfree graphs // Inform. Processing Letters. — 1997. — V. 61. — P. 137-143.

48. Sauer N. On the density of families of sets // J. of Combinatorial Theory, Ser. A. — 1972. — V. 13. — P. 145-147.

49. Schaefer T. J., The complexity of satisfiability problems, Proc. 10th Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York. — 1978. — 216-226.

50. Shelah S. A combinatorial problem, stability and order for models and theories in infinitary languages // Pacific Journal of Mathematics. — 1972. — V. 41. — P. 241-261.у