ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 30431
Тема:    [ Обход графов ]
Сложность: 2
Классы: 6,7
В корзину
Прислать комментарий

Условие

Имеется группа островов, соединённых мостами так, что от каждого острова можно добраться до любого другого. Турист обошёл все острова, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведёт с Троекратного, если турист
  а) не с него начал и не на нём закончил?
  б) с него начал, но не на нём закончил?
  в) с него начал и на нём закончил?


Решение

а) На Троекратый турист 3 раза зашёл и 3 раза с него вышел, то есть использовал 6 мостов.

б) В этом случае турист зашел на остров дважды, а вышел трижды.


Ответ

а) 6 мостов;  б) 5 мостов;  в) 4 моста.

Источники и прецеденты использования

книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: "АСА"
Издание 1
глава
Номер 6
Название Графы-1
Тема Теория графов
задача
Номер 020

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .