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

• Сорочан, Сергей Владимирович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Сорочан, Сергей Владимирович

ВВЕДЕНИЕ

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат физико-математических наук Сорочан, Сергей Владимирович, 2006 год

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.у