Задача 30431

Тема:    [ Обход графов ]

Сложность: 2 Классы: 6,7

Условие

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

Решение

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

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

Ответ

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

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

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