Редактирование: Верхние и нижние оценки хроматического числа

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 8: Строка 8:
 
*Произвольную вершину <tex>u</tex>, покрасим в цвет <tex>dist(v,u)</tex> <tex>  \bmod </tex> <tex> (\Delta + 1)</tex>, где <tex>dist(v,u)</tex>{{---}} расстояние между вершинами <tex>u,v</tex> в графe <tex>T</tex>.
 
*Произвольную вершину <tex>u</tex>, покрасим в цвет <tex>dist(v,u)</tex> <tex>  \bmod </tex> <tex> (\Delta + 1)</tex>, где <tex>dist(v,u)</tex>{{---}} расстояние между вершинами <tex>u,v</tex> в графe <tex>T</tex>.
 
Докажем от противного, что после выполнения описанного алгоритма граф <tex>G</tex> будет правильно раскрашен.
 
Докажем от противного, что после выполнения описанного алгоритма граф <tex>G</tex> будет правильно раскрашен.
Предположим, что после выполнения алгоритма покраски в графе существует ребро, соединяющее вершины <tex> a, b </tex> одного цвета. Пусть <tex>color(v)</tex> {{---}} цвет вершины после выполнения алгоритма раскраски. Заметим, что для произвольной вершины графа <tex>p</tex>, <tex>dist(v,p) = color(p) + n(\Delta + 1)</tex> , <tex>n \geqslant 0 </tex>. Тогда, <tex>dist(v,a) - dist(v,b) = k(\Delta + 1)</tex>. Поскольку в дереве dfs между вершинами находящимися на одинаковом расстоянии от корня нет перекрестных ребер, то <tex> k \geqslant 1</tex>. То есть, вершины <tex>a, b</tex> лежат на простом цикле длины по крайней мере <tex>\Delta + 2</tex>. Получается противоречие с условием потому, что длина максимального простого цикла получается больше чем <tex>\Delta</tex>.
+
Предположим, что после выполнения алгоритма покраски в графе существует ребро, соединяющее вершины <tex> a, b </tex> одного цвета. Пусть <tex>color(v)</tex> {{---}} цвет вершины после выполнения алгоритма раскраски. Заметим, что для произвольной вершины графа <tex>p</tex>, <tex>dist(v,p) = color(p) + n(\Delta + 1)</tex> , <tex>n \geqslant 0 </tex>.Тогда, <tex>dist(v,a) - dist(v,b) = k(\Delta + 1)</tex>. Поскольку в дереве dfs между вершинами находящимися на одинаковом расстоянии от корня нет перекрестных ребер, то <tex> k \geqslant 1</tex>. То есть, вершины <tex>a, b</tex> лежат на простом цикле длины по крайней мере <tex>\Delta + 2</tex>. Получается противоречие с условием потому, что длина максимального простого цикла получается больше чем <tex>\Delta</tex>.
 
Таким образом в графе <tex>G</tex> после выполнения алгоритма раскраски  нет вершин одного цвета соединенных ребром и при этом каждая вершина покрашена в один из <tex>\Delta + 1</tex>, то есть <tex>G</tex> правильно раскрашен в <tex>\Delta + 1</tex> цвет, следовательно <tex>\chi(G) \leqslant \Delta(G) + 1</tex>
 
Таким образом в графе <tex>G</tex> после выполнения алгоритма раскраски  нет вершин одного цвета соединенных ребром и при этом каждая вершина покрашена в один из <tex>\Delta + 1</tex>, то есть <tex>G</tex> правильно раскрашен в <tex>\Delta + 1</tex> цвет, следовательно <tex>\chi(G) \leqslant \Delta(G) + 1</tex>
 
   
 
   

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: