Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый соединялся ровно с пятнадцатью?
Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый соединялся ровно с пятнадцатью?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
По теореме о рукопожатиях сумма степеней вершин равна удвоенному числу рёбер: ∑vdeg(v)=2E\sum_{v}\deg(v)=2E∑v deg(v)=2E. Здесь ∑vdeg(v)=77⋅15=1155\sum_{v}\deg(v)=77\cdot15=1155∑v deg(v)=77⋅15=1155 — нечётное число, а правая часть всегда чётна. Противоречие, следовательно такой граф (даже с параллельными рёбрами или петлями) построить нельзя.