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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
  
Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.
+
{\bf Докажем}, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.
  
 
Построим обход этого граф в ширину из u.
 
Построим обход этого граф в ширину из u.
 
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
  

Версия 20:22, 9 декабря 2017