Question

В кабинете информатики 20 компьютеров, которые соединены проводами так, что каждый провод соединяет два компьютера, каждая пара компьютеров соединена не более чем одним проводом и от каждого компьютера отходит не более двух проводов. Нужно закрасить провода (каждый провод целиком одной краской) так, чтобы от каждого компьютера отходили провода разных цветов. Какого наименьшего числа красок достаточно для такой закраски?

Answer 1

Ответ:

2

Пошаговое объяснение:

Answer 2

Для решения этой задачи, давайте рассмотрим возможные варианты соединения компьютеров проводами и попробуем найти минимальное количество красок, которое потребуется для закраски всех проводов.

Максимальное количество проводов, исходящих от одного компьютера, составляет 2. Поскольку каждая пара компьютеров соединена не более чем одним проводом, то количество проводов в сети будет равно количеству пар компьютеров. При этом каждый компьютер будет участвовать в (N-1) парах, где N - общее количество компьютеров.

Таким образом, у нас есть 20 компьютеров и 19 пар, которые требуется соединить проводами.

Посмотрим, как это можно сделать:

• Взяв первый компьютер, мы можем соединить его с 19 другими, и каждый раз это будет новый провод разного цвета. Таким образом, нам понадобится 19 цветов.

В результате, наименьшее число красок, которое потребуется для такой закраски, равно 19.