О раскрасках графов
|
1. Введение 3
2. Частичные функции и раскраски 6
3. Конфигурации и их правильные раскраски 8
4. Динамические раскраски конфигураций 13
5. Асимптотическая точность оценки 20
Список литературы 22
2. Частичные функции и раскраски 6
3. Конфигурации и их правильные раскраски 8
4. Динамические раскраски конфигураций 13
5. Асимптотическая точность оценки 20
Список литературы 22
Мы будем работать с неориентированными графами без петель и кратных рёбер и называть их просто графами. Если разрешены кратные рёбра, мы будем говорить о мультиграфе, но петли всё равно будут запрещены. Как обычно, для вершины v Е V(G) мы будем обозначать через Ng(v) окрестность вершины v, то есть множество вершин, смежных с ней; через A(G) и S(G) мы будем обозначать соответственно максимальную и минимальную степень вершины графа G.
В этой работе мы попытаемся обобщить теорему Брукса [1], утверждающую, что для любого натурального Д ^ 3 и для любого графа G без подграфов вида Кд+1, имеющего Д(G) < Д, верно x(G) < Д, на f-динамические раскраски — модификацию динамических раскрасок, предложенных Монтгомери в [2].
Определение 1. Пусть f: No ^ No — частичная функция. Раскраску графа G будем называть f-динамической, если для каждого p Е Dom f верно следующее: у каждой вершины v Е V(G), имеющей степень deg v ^ p, в её окрестности имеются вершины хотя бы f (р) различных цветов.
Через Xf (G) будем обозначать f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G имеет правильную f-динамическую раскраску в m цветов, или правильную f -динамическую m-раскраску (или +гс>, если такого числа m не существует).
Будем говорить, что G списочно f -раскрашиваем в m цветов, если для любого назначения вершинам G списков цветов из некоторой палитры P существует правильная f-динамическая P-раскраска G, в которой каждая вершина покрашена в некоторый цвет из её списка. Через chf(G) будем обозначать списочное f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G является списочно f-раскрашиваемым в m цветов (или +то, если такого числа m не существует).
Мы будем через {(p1,c1), (p2,c2),... , (pq, cq)} обозначать частичную функцию, для каждого i отображающую pi в ci. В частности,
• 0-динамическая раскраска — это просто раскраска (соответствующее хроматическое и списочное хроматическое число обозначаются X(g) и ch(G));
• {(2, 2)}-динамическая раскраска — это динамическая раскраска графа (соответствующее хроматическое и списочное хроматическое число обозначаются y2(G) и ch2(G));
• {(c, c) }-динамическая раскраска — это c-невырожденная раскраска.
В [4] c-невырожденные раскраски обобщаются до (c,p)-невырожденных раскрасок (в наших терминах — до {(p, ф}-динамических). Там получен следующий аналог теоремы Брукса.
Теорема (Н. В. Гравин, 2009). Пусть G — граф, натуральное Д > 3 таково, что G не содержит подграфа Кд+1 и имеет &(G) С Д. Тогда для любого натурального c ^ 2 выполнено X{(p,c)}(G) С Д, где
p = (с3 + 8c2 + 19c + 6) (c + 1).
Это весьма сильный результат, однако он предлагает большее, чем теорема Брукса, лишь для очень большой палитры (например, при c = 2 условие динамичности накладывается лишь на вершины степеней, не меньших 252, значит, и раскрашивается такой граф не менее чем в 252 цвета). В нескольких работах по динамическим раскраскам были применены более тонкие методы, позволяющие сильно сократить эту границу. Например, в следующих работах доказано существование раскрасок при условии, что число используемых цветов на один больше, чем максимальная степень графа.
Теорема (H.-J. Lai, B. Montgomery, H. Poon, 2003, [3]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда y2(G) С Д + 1.
Теорема (S. Akbari, M. Ghanbari, S. Jahanbekam, 2009, [5]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда ch2 (G) С Д + 1.
В 2010 году в [6] Карпов доказал динамический вариант теоремы Брукса (то есть использовал в динамической раскраске графа Д^) цветов), начиная с максимальной степени восемь; в [7] он усилил этот результат, доказав его же для всех Д ^ 6.
Теорема (Д. В. Карпов, 2016, [7]). Для графа H назовём его 1-подразбиением граф, получаемый из H заменой нескольких (возможно, нуля) рёбер на цепочки длины два (с каждой такой цепочкой добавляется одна новая вершина степени два). Обозначим через Kn класс всех 1-подразбиений графа Kn.
Пусть G — граф, натуральное Д > 6 таково, что Д(С) < Д.
1. Если G имеет компоненту связности из £д+1, то y2(G) = Д + 1.
2. Если G не имеет компоненты связности из £д+1, то y2(G) < Д.
В этой работе мы докажем следующий результат.
Теорема 1. Пусть /(2,k) — частичная функция {(2, 2), (k, 3)}.
Пусть G — граф, натуральное число Д таково, что Д^) < Д, k е {3, 4, 5,6}. Обозначим g(k) = {(3, 6), (4,13), (5, 31)}. Тогда:
• при k е {3, 4, 5} и Д > g(k) выполнено chy(2fc) (G) < |~| Д + 1;
• при k = 6, а также при k е {3,4,5} и Д < g(k) выполнено chf(2,k) (G) < max{3k + 1, Д + 7 + Ге(Д, k)]}.
Функция е(Д, k) = 0(имеет вид
24k - 84
Д + 13 - 2k + V4k2 + Д2 + 1 - 4ЕД - 4k + 26Д ’
В частности, при k = 6 выполнена оценка
60
' ' < ma^19,Д + 7+ Д + 1 + 7(Д + 1)2 + 120 [
и верно chf(2 6) (G) < Д + 8 при Д > 28.
Следствие 1. Пусть G — граф, натуральное число Д > 28 таково, что Д^) < Д. Тогда chf(2 6)(G) < Д + 8.
Следствие 2. Пусть G — граф, натуральное число Д таково, что Д^) < Д. Тогда верны следующие неравенства:
• chf(2,3) (G) < 2Д + 1 при Д > 6;
• chf(2,4) (G) < |"|A"| + 1 при A > 13;
• chf(2 5) (G) < I"6 A"| + 1 при A > 31;
При k E {3, 6} мы докажем, что этот результат асимптотически точен по A (и отличается от точного на некоторую константу).
Теорема 2. Пусть k E {3, 6}. Тогда существует бесконечная серия графов G^,k, параметризованная натуральным числом A, что A(G^,k) =
A и Xf(2,k) (G^,k) = Chf(2,k) (G^,k) = 6 A + ©Д^+^(1).
В этой работе мы попытаемся обобщить теорему Брукса [1], утверждающую, что для любого натурального Д ^ 3 и для любого графа G без подграфов вида Кд+1, имеющего Д(G) < Д, верно x(G) < Д, на f-динамические раскраски — модификацию динамических раскрасок, предложенных Монтгомери в [2].
Определение 1. Пусть f: No ^ No — частичная функция. Раскраску графа G будем называть f-динамической, если для каждого p Е Dom f верно следующее: у каждой вершины v Е V(G), имеющей степень deg v ^ p, в её окрестности имеются вершины хотя бы f (р) различных цветов.
Через Xf (G) будем обозначать f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G имеет правильную f-динамическую раскраску в m цветов, или правильную f -динамическую m-раскраску (или +гс>, если такого числа m не существует).
Будем говорить, что G списочно f -раскрашиваем в m цветов, если для любого назначения вершинам G списков цветов из некоторой палитры P существует правильная f-динамическая P-раскраска G, в которой каждая вершина покрашена в некоторый цвет из её списка. Через chf(G) будем обозначать списочное f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G является списочно f-раскрашиваемым в m цветов (или +то, если такого числа m не существует).
Мы будем через {(p1,c1), (p2,c2),... , (pq, cq)} обозначать частичную функцию, для каждого i отображающую pi в ci. В частности,
• 0-динамическая раскраска — это просто раскраска (соответствующее хроматическое и списочное хроматическое число обозначаются X(g) и ch(G));
• {(2, 2)}-динамическая раскраска — это динамическая раскраска графа (соответствующее хроматическое и списочное хроматическое число обозначаются y2(G) и ch2(G));
• {(c, c) }-динамическая раскраска — это c-невырожденная раскраска.
В [4] c-невырожденные раскраски обобщаются до (c,p)-невырожденных раскрасок (в наших терминах — до {(p, ф}-динамических). Там получен следующий аналог теоремы Брукса.
Теорема (Н. В. Гравин, 2009). Пусть G — граф, натуральное Д > 3 таково, что G не содержит подграфа Кд+1 и имеет &(G) С Д. Тогда для любого натурального c ^ 2 выполнено X{(p,c)}(G) С Д, где
p = (с3 + 8c2 + 19c + 6) (c + 1).
Это весьма сильный результат, однако он предлагает большее, чем теорема Брукса, лишь для очень большой палитры (например, при c = 2 условие динамичности накладывается лишь на вершины степеней, не меньших 252, значит, и раскрашивается такой граф не менее чем в 252 цвета). В нескольких работах по динамическим раскраскам были применены более тонкие методы, позволяющие сильно сократить эту границу. Например, в следующих работах доказано существование раскрасок при условии, что число используемых цветов на один больше, чем максимальная степень графа.
Теорема (H.-J. Lai, B. Montgomery, H. Poon, 2003, [3]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда y2(G) С Д + 1.
Теорема (S. Akbari, M. Ghanbari, S. Jahanbekam, 2009, [5]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда ch2 (G) С Д + 1.
В 2010 году в [6] Карпов доказал динамический вариант теоремы Брукса (то есть использовал в динамической раскраске графа Д^) цветов), начиная с максимальной степени восемь; в [7] он усилил этот результат, доказав его же для всех Д ^ 6.
Теорема (Д. В. Карпов, 2016, [7]). Для графа H назовём его 1-подразбиением граф, получаемый из H заменой нескольких (возможно, нуля) рёбер на цепочки длины два (с каждой такой цепочкой добавляется одна новая вершина степени два). Обозначим через Kn класс всех 1-подразбиений графа Kn.
Пусть G — граф, натуральное Д > 6 таково, что Д(С) < Д.
1. Если G имеет компоненту связности из £д+1, то y2(G) = Д + 1.
2. Если G не имеет компоненты связности из £д+1, то y2(G) < Д.
В этой работе мы докажем следующий результат.
Теорема 1. Пусть /(2,k) — частичная функция {(2, 2), (k, 3)}.
Пусть G — граф, натуральное число Д таково, что Д^) < Д, k е {3, 4, 5,6}. Обозначим g(k) = {(3, 6), (4,13), (5, 31)}. Тогда:
• при k е {3, 4, 5} и Д > g(k) выполнено chy(2fc) (G) < |~| Д + 1;
• при k = 6, а также при k е {3,4,5} и Д < g(k) выполнено chf(2,k) (G) < max{3k + 1, Д + 7 + Ге(Д, k)]}.
Функция е(Д, k) = 0(имеет вид
24k - 84
Д + 13 - 2k + V4k2 + Д2 + 1 - 4ЕД - 4k + 26Д ’
В частности, при k = 6 выполнена оценка
60
' ' < ma^19,Д + 7+ Д + 1 + 7(Д + 1)2 + 120 [
и верно chf(2 6) (G) < Д + 8 при Д > 28.
Следствие 1. Пусть G — граф, натуральное число Д > 28 таково, что Д^) < Д. Тогда chf(2 6)(G) < Д + 8.
Следствие 2. Пусть G — граф, натуральное число Д таково, что Д^) < Д. Тогда верны следующие неравенства:
• chf(2,3) (G) < 2Д + 1 при Д > 6;
• chf(2,4) (G) < |"|A"| + 1 при A > 13;
• chf(2 5) (G) < I"6 A"| + 1 при A > 31;
При k E {3, 6} мы докажем, что этот результат асимптотически точен по A (и отличается от точного на некоторую константу).
Теорема 2. Пусть k E {3, 6}. Тогда существует бесконечная серия графов G^,k, параметризованная натуральным числом A, что A(G^,k) =
A и Xf(2,k) (G^,k) = Chf(2,k) (G^,k) = 6 A + ©Д^+^(1).
Возникли сложности?
Нужна помощь преподавателя?
Помощь студентам в написании работ!
Цель, которая была достигнута при выполнении работы, заключалась в обобщении теоремы Брукса. Исследования осуществлялись с использованием неориентированных графов без петель и кратных рёбер.
[1] Brooks R. L., On colouring the nodes of network. Proc. Cambridge Philos. Soc. (1941) 37, 194-197.
[2] Montgomery B., Dynamic colouring, Ph. D. Dissertation. West Virginia Univ., 2001.
[3] H.-J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003) 193-201.
[4] Н. В. Гравин, Невырожденные раскраски в теореме Брукса, Дискрет. матем., 2009, том 21, выпуск 4, 105-128.
[5] S. Akbari, M. Ghanbari, S. Jahanbekam, On the list dynamic coloring of graphs, Discrete Applied Mathematics, 2009, vol. 157, 3005-3007.
[6] Д. В. Карпов, Динамические правильные раскраски вершин графа, Записки научных семинаров ПОМИ, 2010, том 381, выпуск 4, 47-77.
[7] D. V. Karpov, An analog of Brooks’ Theorem for dynamic colorings, Moscow Journal of Combinatorics and Number Theory, 2016, vol. 6, iss. 1, 25-63.
[8] D. K. Ray-Chaudhuri, R. M. Wilson, Solution of Kirkman’s schoolgirl problem, Combinatorics, University of California, Los Angeles, 1968, Proceedings of Symposia in Pure Mathematics, Providence, Rhode Island: American Mathematical Society, XIX: 187-203.
[2] Montgomery B., Dynamic colouring, Ph. D. Dissertation. West Virginia Univ., 2001.
[3] H.-J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003) 193-201.
[4] Н. В. Гравин, Невырожденные раскраски в теореме Брукса, Дискрет. матем., 2009, том 21, выпуск 4, 105-128.
[5] S. Akbari, M. Ghanbari, S. Jahanbekam, On the list dynamic coloring of graphs, Discrete Applied Mathematics, 2009, vol. 157, 3005-3007.
[6] Д. В. Карпов, Динамические правильные раскраски вершин графа, Записки научных семинаров ПОМИ, 2010, том 381, выпуск 4, 47-77.
[7] D. V. Karpov, An analog of Brooks’ Theorem for dynamic colorings, Moscow Journal of Combinatorics and Number Theory, 2016, vol. 6, iss. 1, 25-63.
[8] D. K. Ray-Chaudhuri, R. M. Wilson, Solution of Kirkman’s schoolgirl problem, Combinatorics, University of California, Los Angeles, 1968, Proceedings of Symposia in Pure Mathematics, Providence, Rhode Island: American Mathematical Society, XIX: 187-203.
Работу высылаем на протяжении 30 минут после оплаты.
Подобные работы
- Раскраска графов и задача построения расписания с ограничениями
Бакалаврская работа, информационные системы. Язык работы: Русский. Цена: 4650 р. Год сдачи: 2017 - Невырожденные раскраски графов
Бакалаврская работа, математика. Язык работы: Русский. Цена: 4700 р. Год сдачи: 2023 - Программная реализация алгоритма решения задачи о раскраске
Бакалаврская работа, программирование. Язык работы: Русский. Цена: 4550 р. Год сдачи: 2020 - Разработка информационной системы «Студграф»
Дипломные работы, ВКР, эвм. Язык работы: Русский. Цена: 5900 р. Год сдачи: 2016 - Алгоритмы теории графов (Теория графов, вариант 12)
Курсовые работы, математика. Язык работы: Русский. Цена: 700 р. Год сдачи: 2019 - МЕТОДИКА ПРЕПОДАВАНИЯ ЭЛЕМЕНТОВ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ ПО МАТЕМАТИКЕ
Дипломные работы, ВКР, педагогика. Язык работы: Русский. Цена: 4235 р. Год сдачи: 2018 - ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ
Дипломные работы, ВКР, информатика. Язык работы: Русский. Цена: 4355 р. Год сдачи: 2017 - Разработка модуля «расписание» для информационной системы среднего образовательного учреждения МАОУ Гимназия №13 г.Красноярск
Бакалаврская работа, информационные системы. Язык работы: Русский. Цена: 4900 р. Год сдачи: 2016 - ЗАДАЧИ НА КЛЕТЧАТОЙ БУМАГЕ В НАЧАЛЬНОЙ ШКОЛЕ
Дипломные работы, ВКР, психология. Язык работы: Русский. Цена: 5970 р. Год сдачи: 2016
Заказать работу
Заявка на оценку стоимости
Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы
Каталог работ (131311)
- Бакалаврская работа (31672)
- Диссертация (960)
- Магистерская диссертация (18563)
- Дипломные работы, ВКР (53438)
- Главы к дипломным работам (2110)
- Курсовые работы (9693)
- Контрольные работы (6189)
- Отчеты по практике (1308)
- Рефераты (1451)
- Задачи, тесты, ПТК (616)
- Ответы на вопросы (154)
- Статьи, Эссе, Сочинения (916)
- Бизнес-планы (49)
- Презентации (101)
- РГР (84)
- Авторефераты (РГБ) (1691)
- Диссертации (РГБ) (1879)
- Прочее (437)
Новости
06.01.2018
Помощь студентам и аспирантам в выполнении работ от наших партнеров
Помощь в выполнении учебных и научных работ на заказ ОФОРМИТЬ ЗАКАЗ
дальше»» Все новости
Статьи
- Где лучше заказывать диссертации и дипломные?
- Выполнение научных статей
- Подготовка диссертаций
- Подводные камни при написании магистерской работы
- Помощь в выполнении дипломных работ
»» Все статьи
Заказать работу
Заявка на оценку стоимости
Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы