Функция неплотности и обобщенные числа Рамсея

• Автор: Полякова, Ольга Павловна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Ярославль
• Количество страниц: 88 с.

1.1. Основные определения

1.2 Характеризация графов с помощью функции неплотности

1.3. Алгоритм нахождения функции плотности

Глава 2. Различные оценки функции неплотности

2.1.0 росте функции неплотности графа

2.2. Оценки функции неплотности

2.3. Поведение функции неплотности при операциях над графами Глава 3. Оценки обобщенных чисел Рамсея различных классов графов

3.1 Оценки чисел Рамсея рберных графов

3.2 Оценки чисел Рамсея тотальных графов

3.3 Числа Рамсея графов пересечений геометрических множеств

Литература


Теорема 1. Если р 1,7 ря, 7 к, то множество вершин У графа С можно разбить на две такие части VI и У2, что У оо и дС2 к для подграфа С2 на множестве У2. Третий параграф первой главы содержит алгоритм для нахождения функции плотности графа. Задача нахождения значения функции плотности является МРполной, так как включает в себя задачу построения минимальной д. Поэтому особое значение приобретают предварительные вычисления, позволяющие ограничить перебор, а значит уменьшить трудоемкость данного алгоритма. Вторая глава посвящена различным оценкам функции неплотности. В первом параграфе второй главы исследуется поведение функции неплотности, если известно ее значение в некоторой точке. Первый результат в этом направлении был получен в работе 9. Сформулируем основной результат этого параграфа. Теорема 2. Еслир. Рамсея. Яд 4 ,3,2 число Рамсея. При доказательстве теоремы 2. Лемма 2. Если граф С обладает р. П вершинах имеет неплотность С А, то подграф 7Сч обладает р щ, д Асвойством. Лемма 2. Если рд,3Кп р, то рд,Ст р 4 п. Лемма 2. Если рС 4 и в графе С каждые к к 2 треугольников имеют общую вершину, то из множества вершин графа можно выкинуть ЗА 1 так, что останется граф без треугольников. В данном параграфе приводятся и некоторые другие, полученные в этом направлении результаты. Теорема 2. Теорема 2. Зд 2, Ед4 1,3,2, где Яд 4 1,3,2 число Рамсея. Во втором параграфе доказаны оценки функции неплотности через различные характеристики графа последовательность степеней, число вершин и ребер.