Консультация № 177115
07.03.2010, 10:55
0.00 руб.
0 1 1
В городе 15 телефонов, каждый из которых соединен проводами не менее чем с 7-ю другими. Докажите, что сообщение может быть передано от одного телефона до любого другого.

Обсуждение

давно
Профессор
230118
3054
07.03.2010, 11:43
общий
это ответ
Здравствуйте, Гуревич Александр Львович.

Это вопрос про связность графов. Если телефон может связаться с другим телефоном, он может связаться и с теми, с которыми тот связан. Предположим, два телефона не связаны. Тогда в первую группу занесем первый телефон и 7 связанных с ним, во вторую - второй телефон и 7 связанных с ним. Для этого нужно 16, а у нас всего 15. Значит, группа всего одна.
5
Совершенно верно! Задача решается с помощью графов.
Форма ответа