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

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

Версия 19:57, 9 декабря 2017