авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

СОРОЧАН Сергей Владимирович ИССЛЕДОВАНИЕ КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК НАСЛЕДСТВЕННЫХ КЛАССОВ ОРИЕНТИРОВАННЫХ И ЦВЕТНЫХ ГРАФОВ 01.01.09 дискретная математика и математическая кибернетика

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

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

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

Научный консультант:

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

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

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

д.т.н., проф. Коган Д. И.

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

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

Защита диссертации состоится “ 21 ” сентября 2006 г. в 16-20 часов на заседании диссертационного совета Д 212.166.06 при ННГУ им. Н. И. Лобачевского по адресу:

603950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

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

Ученый секретарь диссертационного совета Д 212.166. к.ф.-м.н, доцент Лукьянов В. И.

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

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

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

При решении вопросов количественного анализа в работе принят асимптотический подход, основанный на понятии энтропии множества графов. Энтропия представляет собой “логарифмическую плотность” предел отношения логарифма числа графов с n вершинами из данного множества к логарифму числа всех n-вершинных графов заданного типа. Существование этого предела является одним из общих свойств наслед ственных классов (существование энтропии наследственных классов обыкновенных гра фов было ранее установлено В. Е. Алексеевым1, одним из результатов данной работы является доказательство существования энтропии наследственных классов ориентиро ванных и цветных графов). Указанное свойство, а также некоторые другие свойства наследственных классов графов аналогичны свойствам инвариантных классов булевых функций, введенных и изученных С. В. Яблонским2. Однако между семействами наслед ственных классов графов и инвариантных классов булевых функций имеются и суще ственные различия. Так, С. В. Яблонский доказал, что параметр, аналогичный энтропии наследственных классов, для инвариантных классов может принимать любые значения из отрезка [0, 1]. Позднее В. Е. Алексеев установил, что множество допустимых значений энтропии наследственных классов обыкновенных графов счетно (оно состоит только из Алексеев В. Е. Наследственные классы и кодирование графов // В сб. Проблемы кибернетики, вып. 39 / Под ред. С. В. Яблонского. М.: Наука, 1982. С. 151–164.

Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // В сб.

Проблемы кибернетики, вып. 2 / Под ред. А. А. Ляпунова. М.: Физматгиз, 1959. С 75–121.

чисел вида 1 k ), доказал существование и дал исчерпывающее описание минимальных по включению классов с заданным значением энтропии3.

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

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



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

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

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

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

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

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

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

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

Выявить определенные общие закономерности и установить индивидуальные особенно сти результатов и методов решения задач.

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

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 12 работ, список которых приво дится в конце автореферата. Среди них 6 статей, опубликованных в Центральной науч ной печати, а именно: 4 статьи в журнале “Дискретный анализ и исследование операций”, одна статья в журнале “Дискретная математика” и одна статья в журнале “Discrete Math.

Appl.”. Остальные публикации являются тезисами докладов и включены в сборники тру дов научных конференций и семинаров. Общее количество страниц статей, опубликован ных в Центральной научной печати, составляет 103 страницы. В тезисах докладов на научных конференциях и семинарах опубликовано 26 страниц.

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

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

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

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

В §1 с помощью леммы о равномерном покрытии5 доказывается, что для любых бесконечных наследственных классов X орграфов и Y q-цвтных графов существуют е пределы logq |Yn | log2 |Xn | hdir (X ) h(X ) = lim и h[q] (Y) h(Y) = lim, n n(n 1) n n называемые энтропиями классов X и Y соответственно. Здесь Xn (соответственно Yn ) множество всех ориентированных (q-цвтных) графов из X (из Y) с множеством е вершин {1,..., n}.

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

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

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

Пусть E класс всех пустых орграфов (графов с пустым множеством дуг), C класс всех полных орграфов (в полном орграфе каждая упорядоченная пара вершин является дугой), T класс всех транзитивных турниров (орграфов, в которых каждая пара вершин соединена точно одной дугой и из существования дуг (a, b) и (b, c) следует существование дуг (a, c)). Эти три класса будем называть простейшими.

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

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

Пусть U и V непересекающиеся множества. Двудольным орграфом с левой долей U, правой долей V и множеством дуг E будем называть тройку (U, V, E), где E (U V ) (V U ). Введем понятие типа P (x, y) пары вершин (x, y) U V по отношению к двудольному орграфу (U, V, E):

a (от слова “absent”),если (x, y) E и (y, x) E, l (от слова “left”), если (x, y) E, а (y, x) E, P (x, y) = r (от слова “right”), если (x, y) E, а (y, x) E, d (от слова “double”), если (x, y) E и (y, x) E.

Bollobs B., Thomason A. Projections of bodies and hereditary properties of hypergraphs // Bulletin of a the London Mathematical Society. 1995. v. 27. p. 417–424.

Двудольный орграф может быть задан матрицей, строкам которой поставлены в со ответствие вершины левой доли, столбцам вершины правой доли, а на пересечении строки, соответствующей вершине a, со столбцом, соответствующим вершине b, на ходится тип пары (a, b). Эту матрицу будем называть матрицей типов двудольного орграфа. Для непустого множества M {a, l, r, d} через B(M ) обозначим класс таких двудольных орграфов, у которых все элементы матрицы типов принадлежат M.

Пусть G = (V, E) орграф, а U1 и U2 непересекающиеся подмножества мно жества V. Обозначим через G U1, U2 двудольный орграф (U1, U2, E ), где E = E ((U1 U2 ) (U2 U1 )).

Пополнением двудольного орграфа B = (U, V, E) назовем любой орграф G = (U V, E ), такой, что G U, V = B, E E.

Пусть X1 и X2 множества орграфов, а Y {a, l, r, d}. Через X1 Y X2 обозначим совокупность всех орграфов G = (V, E), множество вершин которых можно разбить на две такие части V1 и V2, что G V1 X1, G V2 X2, а G V1, V2 B(Y ).

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

(1) h(X ) 0;

(2) h(X ) 1/4;

(3) существует такое Y {a, l, r, d}, |Y | = 2, что каждый двудольный орграф из B(Y ) имеет пополнение, принадлежащее X ;

(4) существуют такие наследственные классы ориентированных графов X1, X {E, C, T } и такое Y {a, l, r, d}, |Y | = 2, что X1 Y X2 X.

Среди классов вида X1 Y X2, фигурирующих в утверждении (4), имеется ровно различных. Это классы, для которых множества X1, X2 и Y выбираются одним из следующих способов:

X1, X2 {E, C, T }, а Y = {a, l} или Y = {d, l} (число попарно различных классов такого вида равно 18);

(X1, X2 ) это любое двухэлементное сочетание с повторениями из множества {E, C, T }, а Y = {a, d} или Y = {r, l} (имеется 12 попарно различных классов та кого вида).

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

е Пусть V и U непересекающиеся множества. Двудольным q-графом с долями V и U будем называть тройку (V, U, C), где C : V U Q = {1,..., q}. Для множества P Q обозначим через B(P ) множество всех таких двудольных q-графов, у которых C(V U ) P.

Пополнением двудольного q-графа G = (V, U, C) назовем любой q-граф H = (V U, C ), такой, что отображение C совпадает с C на множестве V U. Пополнение, в котором C (x, y) = для всех (x, y) V (2) и C (x, y) = для всех (x, y) U (2), обозначим через G[, ]. Для множества P Q и цветов, Q определим множество B(P,, ) = {G[, ] : G B(P )}.

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

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

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

(1) h(X ) 0;

(2) h(X ) 1 logq 2;

(3) существует такое множество P Q, |P | = 2, что B(P ) C(X );

(4) существует такое множество P Q, |P | = 2 и такие, Q, что B(P,, ) X.

Следствие 3. Существует 1 q 2 (q 2 1) минимальных наследственных классов q графов с энтропией, равной 1 logq 2. Ими являются в точности все классы вида B(P,, ), где, Q, а P Q, |P | = 2.

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

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

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

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

Пусть Y q Y наследственный класс двудольных q-графов. Обозначим через Yn1,n2 множество двудольных q-графов из Y, у которых V = {1, 2,..., n1 }, U = {n1 + 1, n1 + 2,..., n1 + n2 }. Доказано существование двойного предела logq |Yn1,n2 | hB (Y) = nlim, n1 n n называемого двудольной энтропией класса Y. Справедлива Теорема 9. Двудольная энтропия hB (Y) любого бесконечного класса Y двудольных q-цвтных графов принимает только значения из множества {0 = е logq 1, logq 2,..., logq (q 1), logq q = 1}.

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

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

Теорема 10. Двудольная энтропия log4 |Yn1,n2 | hB (Y) = nlim n1 n n бесконечного наследственного класса Y двудольных орграфов существует и принимает значения из множества {log4 1 = 0, log4 2 = 1/2, log4 3 = (1/2) log2 3, log4 4 = 1}.

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

Глава II нацелена на решение вопросов алгоритмической сложности. Здесь рассмат ривается задача распознавания принадлежности заданного графа определенному классу.

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

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

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

Поэтому достаточно решить задачи характеризации и распознавания только для та ких из тридцати классов, перечисленных в главе I, ни один из которых не является дополнением и обращением другого. Эти задачи решаются для классов вида X1 Y X2, для которых множества X1, X2 и Y выбираются одним из следующих способов:

X1 = X2 = E, а Y = {a, l}, или Y = {a, d}, или Y = {l, r}, или Y = {d, l} (4 класса);

X1 = E, X2 = C, а Y = {a, l}, или Y = {a, d}, или Y = {l, r} (3 класса);

X1 = E, X2 = T, а Y = {a, l}, или Y = {a, d}, или Y = {l, r}, или Y = {d, l} (4 класса);

X1 = X2 = T, а Y = {a, l}, или Y = {a, d}, или Y = {l, r} (3 класса).

В §§2–6 проводится исследование задач характеризации и распознавания для каждо го из указанных классов, за исключением класса T lrT. В §2 это делается для классов, взаимно однозначно соответствующих классам обыкновенных двудольных и расщепля емых графов, в §§3 и 4 для оставшихся классов вида EY E и EY C (|Y | = 2) соответственно, а в §§5 и 6 для классов EY T и двух классов вида T Y T (|Y | = 2) соответственно. Установлено, что задача распознавания орграфов из всех классов, кроме T lrT, разрешима за полиномиальное время.

В §7 проводится исследование последнего оставшегося класса T lrT, названного клас сом транзитивно-двудольных турниров. Для определения сложности задачи распозна вания орграфов из этого класса была рассмотрена следующая вспомогательная зада ча, называемая задачей о (p, r)-раскраске гиперграфа. Дан r-однородный гиперграф F = (V (F ), E(F )), т.е. гиперграф, в котором каждое гиперребро e E(F ) является одним из r-элементных подмножеств множества V (F ). Требуется ответить на вопрос, существует ли такое множество U V (F ), что в любом гиперребре e E(F ) имеется в точности p вершин, принадлежащих множеству U, т.е. |U e| = p.

Известно6, что задача о (p, r)-раскраске гиперграфа является NP-полной при всех r 3 и таких p, что 1 p r. Используем этот результат при p = 2, r = 4.

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

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

Schaefer T. J., The complexity of satisability problems, Proc. 10th Ann. ACM Symp. on Theory of Computing, Assoc. for Computing Machinery, New York. 1978. 216–226.

Farrugia A., Vertex-partitioning into xed additive induced-hereditary properties is NP-hard // Electron.

J. Combin. 2004. V. 11(1) # 46. 9 p.

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

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

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

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

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

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

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

Пусть для каждой пары i, j, где 1 i, j k, i j и k 2, при i = j выбран некоторый бесконечный наследственный класс X ii q-графов, а при i = j некоторый бесконечный наследственный класс X ij двудольных q-графов. Полагаем X ji = X ij при любых i j. Множество всех выбранных классов обозначим через X (k). Тогда k k композицией C(X (k) ) = X ij i,j=1 наследственных классов q-графов из X (k) назовем Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов.

Москва: Наука, гл. ред. физ.-мат. лит., 1990.

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

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

совокупность таких q-графов G, что множество вершин в G можно разбить на непе ресекающиеся подмножества V1,..., Vk (некоторые из них могут быть пустыми) так, что G Vi X ii, G Vi, Vj X ij при всех i = j, i, j = 1,..., k. Классы X 11,..., X kk будем называть секциями k-композиции C(X (k) ).

Каждой k-композиции C(X (k) ) поставим в соответствие симметрическую квадрат ную матрицу H(k) H = (hij ) порядка k, в которой hii = h(X ii ), а hij = hB (X ij ), i = j, i, j = 1,..., k. Матрицу H(k) назовем матрицей энтропий k-композиции C(X (k) ).

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

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

k k h C(X (k) ) = max hij xi xj xj = 1, xj 0, j = 1,..., k.

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

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

Перепишем полученную в теореме 27 задачу математического программирования в матричной форме: найти max F (x) = x Hx 1 x = 1, x 0. (I) Здесь x = {x1,..., xk }, 1 = {1,..., 1}(k), 0 = {0,..., 0}(k), H матрица энтропий k-композиции C(X (k) ), а запись x 0 означает, что каждая компонента вектора x неотрицательна.

Композицию C(X (k) ) назовем регулярной k-композицией, если для ее матрицы энтропий H выполнены 1 требование максимальности: Q H Q 0 (Q – матрица размера k (k 1), в столбцах которой записаны базисные векторы подпространства решений уравнения 1 x = 0) и 2 условие внутренней допустимости: H 1 1 0 (неравенство понимается покомпо нентно).

Решение задачи ( I ), а следовательно, и проблемы вычисления композиций, достав ляет Теорема 28. Энтропия каждой регулярной k-композиции наследственных классов q-графов вычисляется по формуле k h C(X (k) ) = 1 1 H 1 1 = det H Aij i,j= алгебраическое дополнение к элементу hij ), причем у соответствующей (здесь Aij задачи ( I ) квадратичного программирования имеется единственная точка максимума x = H 1 1 1 H 1 1, лежащая внутри допустимой области D = {x Rk | 1 x = 1, x 0} этой задачи.

Любая нерегулярная композиция не является минимальным (по включению) клас сом среди наследственных классов q-графов с заданным значением энтропии;

энтро пия нерегулярной композиции равна максимальной энтропии целиком содержащейся в ней композиции с меньшим количеством секций, причем у соответствующей задачи ( I ) квадратичного программирования существует точка максимума, лежащая на границе допустимой области D этой задачи.

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

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

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

k-композицию Ci (X (k+1) ), полученную из (k + 1)-композиции C(X (k+1) ) удалением i-й секции, назовем порожденной композицией, i = 1,..., k + 1.

В теореме 29 найдена взаимосвязь между порожденной и порождающей компо зициями. Установлено, что если (k + 1)-композиция C(X (k+1) ) и k-композиция Ck+1 (X (k+1) ) C(X (k) ) являются регулярными, то их энтропии связаны соотношением (1 H 1 h 1) 1, = h H 1 h h h C(X (k+1) ) h C(X (k) ) матрица энтропий композиции C(X (k) ), h = h(X k+1,k+1 ), h где H k-мерный вектор-столбец, такой, что hj,k+1 = hB (X j,k+1 ), j = 1,..., k, 1 = {1,..., 1}(k).

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

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

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

Теорема 31. Пусть C(X (k) ) регулярная k-композиция наследственных классов q-графов из X (k). Тогда ее энтропия удовлетворяет неравенствам max h(X ii ) h C(X (k) ) max hB (X ij ).

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

Для произвольного непустого множества M Q обозначим через O q (M ) O(M ) класс таких q-графов G = (V, C), что C(V (2) ) M. Аналогично для непустого мно жества P Q обозначим через B q (P ) B(P ) множество таких двудольных q графов, для которых C(V U ) P. Нетрудно видеть, что h(O(M )) = logq |M |, а hB (B(P )) = logq |P |.

Композицию C(X (k) ) = X ij k jj i,j=1 назовем правильной k-композицией, если X = O(Mjj ), X ij = B(Mij ) при некоторых непустых Mjj Q, Mij Q, i = j, i, j = 1,..., k.

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

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

во-вторых, установлено существование и приведена характеризация минимальных по включению среди таких композиций;

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

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

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

матрица энтропий регулярной k-композиции C(X (k) ) Теорема 33. Пусть H наследственных классов q-графов из X (k), а C(X (k+1) ) (k + 1)-композиция, порож (k) (k+1) дающая C(X ). Тогда для того, чтобы C(X ) являлась регулярной, необходимо и достаточно выполнение неравенств 1 H 1 h 1 0, h H 1 h h 0, (h H 1 h h) H 1 1 (1 H 1 h 1) H 1 h 0.

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

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

Возникает вопрос, как много существует наследственных классов цветных графов с нулевой и ненулевой энтропией. Ответ на этот вопрос доставляет Теорема 35. Множество фрагментно замкнутых классов q-графов с нулевой энтро пией континуально. Кроме того, если H матрица энтропий регулярной k-композиции, то имеется континуальное семейство наследственных классов q-графов с энтропией, рав ной 1 1 H 1 1.

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

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

Hh Кроме того, если H = матрица энтропий регулярной (k + 1)-композиции hh C(X (k+1) ), порождающей регулярную композицию C(X (k) ) с матрицей энтропий H, то для того, чтобы C(X (k+1) ) имела наименьшую возможную энтропию среди всех композиций, порождающих C(X (k) ), необходимо, чтобы h = 0.

h H Следствие 17. Если H = матрица энтропий регулярной ком (h ) (k+1) позиции C(X ), имеющей наименьшую возможную энтропию среди всех (k + 1) композиций, порождающих регулярную k-композицию C(X (k) ), то вектор h удовле творяет условиям h R, где R = h (h H 1 h h) H 1 1 (1 H 1 h 1) H 1 h 0, 1 H 1 h 1 0, hj,k+1 {logq 2, logq 3,..., logq (q 1), 1}, j = 1,..., k (1 H 1 h 1)2 (1 H 1 h 1) и min =.

h H 1 h (h ) H 1 h hR h H Теорема 37. Пусть H = матрица энтропий регулярной композиции (h ) (k+1) C(X ), имеющей наименьшую возможную энтропию среди всех (k + 1)-композиций, порождающих регулярную k-композицию C(X (k) ). Тогда при любом векторе h высоты k с компонентами из множества {logq 2, logq 3,..., logq (q 1), 1} если h h, h = h, Hh то (k + 1)-композиция C(X (k+1) ) с матрицей энтропий H = не является h регулярной, т. е. h R.

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

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

о Теорема 38. Пусть C(X (k+1) ) регулярная (k + 1)-композиция наследствен ных классов q-графов, (k + 1)-я секция которой сама является регулярной m композицией наследственных классов: X k+1,k+1 = C(Y (m) ). Тогда класс q-графов C((X (k+1) \{X k+1,k+1 }) Y (m) ) является регулярной (k + m)-композицией, имеющей эн тропию, равную энтропии композиции C(X (k+1) ).

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

Фрагментно замкнутый класс X = X (k) назовем минимальной верхней границей k= (k) последовательности X : kN бесконечных наследственных классов q-графов.

Будем говорить, что последовательность X (k) : k N монотонно возрастает, если X (1) X (2)... X (k1) X (k) X (k+1)...

Монотонно возрастающую последовательность X (k) : k N назовем нетривиаль ной, если h(X (1) ) h(X (2) )... h(X (k) )... h(X ).

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

k Лемма 11. При 2 |M | = m q каждый из классов O(M ) является нетривиальной минимальной верхней границей;

соответственно каждое из значений вида logq m, m = 2,..., q является точкой сгущения энтропии.

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

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

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

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

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

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

Теорема 41. Для любого ациклического орграфа D существует такой неориен тированный граф G(D), что в каждом орграфе A(G(D)), полученном из G(D) в результате произвольной ациклической ориентации его ребер, найдется порожденный подграф, изоморфный D.

Из теоремы 41 следует Теорема 42. Энтропия h(X ) любого наследственного класса X, целиком содер жащегося в классе A ациклических орграфов в качестве собственного подмножества, строго меньше 1.

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

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

Публикации по теме диссертации 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. 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.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.