Question

В локальной сети а) 2018, б) 2019 рабочих станций и один сервер. Сможет ли Вася соединить их проводами так, чтобы каждая рабочая станция была соединена ровно с четырьмя компьютерами, одним из которых будет сервер? Это задача! Компьютер это локальный сервер или сервер.

Answer 1

Соединим сперва все станции с сервером, получается, теперь нужно соединить станции так, чтобы каждая была соединена с тремя другими.

а) Расположим станции по кругу, соединим 1 с 1010, 2 с 1011 и так далее (проведём 1009 диаметров), теперь соединим каждую из станций с двумя соседними. Теперь каждая станция соединена с тремя другими.

б) 2019 * 3 = 6057 (сумма степеней всех вершин). 6057 - число нечётное. Тут хорошо бы вспомнить лемму о рукопожатиях (сумма степеней всех вершин графа равна удвоенной сумме рёбер). (С переходом в эту задачу, если на одном конце провода есть станция, она должна быть и на другом конце провода). Так что нельзя.

Ответ: а) Можно. б) Нельзя.

Answer 2

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

Чтобы это сделать, можно использовать структуру сети, называемую "звезда". В центре структуры будет находиться сервер, а каждая рабочая станция будет соединена с сервером по отдельному проводу. Таким образом, каждая рабочая станция будет иметь прямое соединение с сервером и, следовательно, каждая станция будет соединена ровно с четырьмя компьютерами - с самой станцией и тремя другими станциями.

Для случая а) с 2018 рабочими станциями и б) с 2019 рабочими станциями, Васе потребуется 2018 + 4 (сервер) провода для первого случая и 2019 + 4 (сервер) провода для второго случая.