|
|
 |
Условие
20 телефонов соединены проводами так, что каждый провод соединяет два телефона, каждая пара телефонов соединена не более чем одним проводом и от каждого телефона отходит не более двух проводов. Нужно закрасить провода (каждый провод целиком одной краской) так, чтобы от каждого телефона отходили провода разных цветов. Какого наименьшего числа красок достаточно для такой закраски?
Решение
Будем изображать телефоны точками, а соединяющие их провода – отрезками, соединяющими эти точки. Так как из каждой точки выходит не более двух отрезков, то полученный граф распадается на незамкнутые пути и простые циклы Заметим, что незамкнутый путь можно покрасить в два цвета, а простой цикл – в три. Для этого достаточно в незамкнутом пути покрасить отрезки через один, а в цикле покрасить один отрезок в цвет 3, а оставшиеся покрасить через один в цвета 1 и 2. Кроме того, заметим, что если в получившемся графе есть треугольник, то двух цветов не хватит. Итак, искомое число красок равно 3.
Ответ
Три краски.
Замечания
Ср. с задачей 35222.
