Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показаны 4 промежуточные версии 1 участника)
Строка 1: Строка 1:
 +
[[Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graph-with-degree]]
 +
 +
 +
 
<latex>
 
<latex>
 
Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1.
 
Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1.
Строка 10: Строка 14:
  
  
Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.
+
{\bf Докажем}, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.
  
 
Построим обход этого граф в ширину из u.
 
Построим обход этого граф в ширину из u.
 
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
  
 +
\vspace{3mm}
  
 
+
{\bf Пусть} теперь все вершины в графе имеют степень d.
Пусть теперь все вершины в графе имеют степень d.
+
  
 
Рассмотрим вершины b, c смежные с a.
 
Рассмотрим вершины b, c смежные с a.
 
 
Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.
 
Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.
  
Строка 29: Строка 31:
  
 
Теперь в исходном графе покрасим b, c в цвет d.
 
Теперь в исходном графе покрасим b, c в цвет d.
 +
 +
Значит G можно покрасить в d цветов.
 +
 
<\latex>
 
<\latex>
 +
 +
[[Категория:Решения]]

Текущая версия на 15:23, 17 декабря 2017

Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graph-with-degree