Тип 9 № 32 
Графы. Применение графов к решению задач
i
В классе 15 компьютеров. Можно ли их соединить друг с другом так, чтобы каждый компьютер был соединен ровно с пятью другими?
Решение. Будем считать компьютеры вершинами графа, а соединяющие их провода — его ребрами. Из каждой вершины выходит пять проводов, поэтому всего должно выходить 75 проводов. Каждый их них учтен дважды, по одному разу для двух соединенных проводом вершин. Следовательно, проводов должно быть 37,5, а это невозможно.
Ответ: 0
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем