Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Потмогите тут тоже

Амирка Хорошист Ученик (93), на голосовании 3 недели назад
В некотором царстве в дремучем лесу находится таинственное озеро. На озере есть семь островков. С каждого островка выходит один, три или пять мостов. Можно ли зайти на эти островки с берега?
Пояснения обязательны! Ответы да/нет будут аннулированы.
Голосование за лучший ответ
x3 Знаток (274) 1 месяц назад
Если представить озеро как граф, то кувшинки в нем-вершины, а мостики-ребра. Тогда в таком графе сумма степеней вершин всегда будет нечетна, это значит что найдется ребро(мостик), у которого кувшинка есть только с одной стороны, тогда другая его сторона будет выходить на берег. Ответ: Да

Откуда задачи?
Юрий Семыкин Искусственный Интеллект (205597) 1 месяц назад
Не обязательно. Все мосты могут быть между парами островков и ни один к берегу.
Например все пять мостов связывают 1 и 2й островки, остальные не связаны ни между собой ни с берегом.
Вы, похоже, не полностью задачу изложили.
Если чо, посмотрите теория графов, Кёнигбергские мосты. Задача касается вычисления "полустепени" входа/исхода. Наличие пути (и цикла).
Похожие вопросы