Введение к работе
Актуальность темы. Теория графов взяла свое начало в работах Л. Эйлера, Г. Кирхгофа, А. Кэли, В. Гамильтона, С. Жордана и затем приобрела широкое распространение в математической среде. Хроматическое число и размер максимальной клики графа, а также напрямую с ними связанные число кликового покрытия и число вершинной независимости графа, используются в большом количестве задач теории графов. Как известно, вычисление каждой из этих функций является NP-трудной задачей. Кроме того, как показано в работах С. Ароры, если Р Ф NP, эти инварианты не могут за полиномиальное время быть оценены с точностью до множителя п, для наперед заданного є > 0. Это определяет трудность и важность изучения свойств хроматического числа и размера максимальной клики.
Из работ Дж. Мыцельского и А.А. Зыкова известно, что хроматическое число не может быть оценено сверху никакой функцией от размера максимальной клики графа. Одним из подходов к оценке этих величин является разбиение отрезка между ними другими функциями, между которыми существует более тесная связь. Функции со значениями, зажатыми межу числом вершинной независимости и числом кликового покрытия, изучались в работах Л. Ловаса, Д.Е. Кнута, В.Ю. Добрынина.
Для разрешения гипотезы Л. Ловаса и М. Сакса из области коммуникационной сложности, важной является проблема нахождения точной оценки хроматического числа с помощью ранга матрицы смежности графа. С. ван Нуффелен предположил, что хроматическое число непустого графа ограничено сверху рангом матрицы смежности. Это предположение было опровергнуто Н. Алоном и П. Сеймуром. Позже, этот вопрос изучался в работах А. Разборова, Р. Раза, Б. Спикера, Н. Нисана, А. Вигдерсона, Л. Ловаса, А. Котлова, Б. Коденотти, Г. дел Корсо, Г. Манзини.
В данной работе рассматриваются несколько аспектов изучения хроматического числа и размера максимальной клики. Рассмотрены функции, определенные через ранг некоторых матриц, ассоциированных с графом, значения которых зажаты между значениями числа вершинной независимости и числа кликового покрытия. Изучена возможность лучшей оценки границ этого отрезка посредствам таких функций. Рассмотрена связь задач оценки хроматического
РОС. '1ЛЦИ0НАЛЫМЯ
«--5И0ТЕКА
' -''етербург
числа через функции, определенные в терминах рангов. Предложены новые функции, которые позволяют больше узнать об исследуемых инвариантах. Оценены изменения значений числа вершинной независимости и числа кликового покрытия при проведении над графом некоторых операций.
Также в работе предложены специальные классы универсальных графов для множества t-рагкрашиваемых графов. Изучению универсальных графов посвящены работы Р. Радо, Дж.А. Бонди, Ф.Р.К. Чунг, Л.Р. Грехема, П.С. Фиптборна, Л. Батта, Дж. Фридмана, Н. Пипенжера, Л. Бабаи, Дж. Спенсера, Дж.В. Мула, В.Е. Алексеева, В.В. Лозина.
Целью диссертационной работы является исследование некоторых свойств размера максимальной клики, хроматического числа, числа вершинной независимости и числа кликового покрытия обыкновенного графа. Основное внимание в работе уделялось следующим направлениям исследований:
развитию методов оценки размера максимальной клики и хроматического числа;
изучению особенностей функций графа, значения которых зажаты между числом вершинной независимости и числом кликового покрытия;
рассмотрению возможности введения новых функций с целью получения лучших оценок инвариантов графа и раскрытия неизвестных закономерностей;
- нахождению связей с другими известными задачами комбинаторики.
Научная новизна. В диссертационной работе был получен ряд новых
результатов относительно известных функций со значениями из отрезка [at(G), x(G)\. Найдена связь между взаимозависимостью функций со значениями из этого отрезка и задачей ограничения хроматического числа через ранг матрицы смежности графа. Введен ряд новых функций и показано, как с их помощью можно больше узнать про число вершинной независимости, число КЛикового покрытия и соотношение между ними. Изучены свойства трех определенных в работе операций и путем их применения построены универсальные графы специального вида.
Практическая значимость. Работа носит теоретическую направленность. Полученные результаты представляют теоретический и практический интерес. Основная практическая ценность определяется многочисленными приложениями теории графов и, в частности, большой важностью задач оценки хроматического
числа и размера максимальной клики графа.
Основные положения, выносимые на защиту:
Рассмотрена связь между числом вершинной независимости и числом кликового покрытия в некоторых особых случаях.
Показано, что разность между хроматическим числом и рангом графа не может превзойти разность между числом кликового покрытия дополнения графа и значением функции r+(G) более чем на единицу.
Доказано, что любая оценка числа кликового покрытия графа через значение функции r+{G) порождает оценку хроматического числа через ранг графа того же порядка.
Следствием этого результата является тот факт, что число кликового покрытия не может быть ограничено никаким полиномом от значенияг+(С).
Доказано, что число кликового покрытия графа совпадает с минимальной размерностью ортонормального помечивания графа ортами пространства.
Показано, что равенство a{G) = ^(G) влечет совпадение чисел вершинной независимости и кликового покрытия графа G.
Получены результаты, позволяющие оценить число вершинной независимости и число кликового покрытия графа чср<& мипимальпую размерность его еюртонормального помечивания.
Показано, что три изученные операции над графом сохраняют размер максимальной клики и хроматическое число, хотя не сохраняют свойство графа быть совершенным. Получены оценки па число вершинной независимости и число кликового покрытия графов, полученных применением рассматриваемых операций.
Показано, как применением изученных операций можно получить универсальные t-хроматические графы для класса t-дольпых графов.
Апробация работы. Диссертация в целом, а также ее отдельные положения и полученные результаты докладывались на XXXII, ХХХГО я XXXV научпых
конференциях «Процессы управления и устойчивость» факультета прикладной математики и процессов управления (г. Санкт-Петербург, 2001-2004 гг.), на Российской конференции «Дискретный анализ и исследование операций» DAOR'04 (г. Новосибирск, 2004 г.), на семинаре «Дискретная математика» Санкт-Петербургского отделения Математического института им. В.А. Стеклова (г. Санкт-Петербург, 2004 г.), а также на семинарах кафедры технологии программирования факультета ПМ-ПУ СПбГУ.
Публикации. По результатам выполненных исследований опубликовано 5 работ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающею 87 наименований. Общий объем диссертации 128 страниц. Работа содержит 16 рисунков.
Похожие диссертации на Исследование хроматического числа и размера максимальной клики графа
