Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями
Материал из DISCOPAL
| Строка 12: | Строка 12: | ||
Построим обход этого граф в ширину из u. | Построим обход этого граф в ширину из u. | ||
| − | Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень | + | Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей. |
Пусть теперь все вершины в графе имеют степень d. | Пусть теперь все вершины в графе имеют степень d. | ||
<\latex> | <\latex> | ||
Версия 19:57, 9 декабря 2017