Участник: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