Задания
Версия для печати и копирования в MS Word
Тип Д3 № 1009
i

В таб­ли­цах при­ве­де­на про­тя­жен­ность ав­то­ма­ги­стра­лей между со­сед­ни­ми на­се­лен­ны­ми пунк­та­ми. Если пе­ре­се­че­ние стро­ки и столб­ца пусто, то со­от­вет­ству­ю­щие на­се­лен­ные пунк­ты не со­еди­не­ны ав­то­ма­ги­стра­ля­ми. Ука­жи­те номер таб­ли­цы, для ко­то­рой вы­пол­ня­ет­ся усло­вие «Мак­си­маль­ная про­тя­жен­ность марш­ру­та от пунк­та А до пунк­та С не боль­ше 5». Про­тя­жен­ность марш­ру­та скла­ды­ва­ет­ся из про­тя­жен­но­сти ав­то­ма­ги­стра­лей между со­от­вет­ству­ю­щи­ми со­сед­ни­ми на­се­лен­ны­ми пунк­та­ми. При этом любой на­се­лен­ный пункт дол­жен встре­чать­ся на марш­ру­те не более од­но­го раза.

1. 2. 3. 4.

Спрятать решение

Ре­ше­ние.

Вы­чис­лим мак­си­маль­ные длины марш­ру­тов.

 

Схема 1. A-B-D-C (2 + 3 + 3 = 8).

Схема 2. A-B-D-C (2 + 1 + 3 = 6).

Схема 3. A-D-B-C (2 + 2 + 2 = 6).

Схема 4. A-B-С (3 + 2 = 5), A-D-C (1 + 1 = 2).

 

Мак­си­маль­ная про­тя­жен­ность марш­ру­та не пре­вы­ша­ет 5 толь­ко на схеме 4.

 

При­ме­ча­ние. Не­об­хо­ди­мо найти путь мак­си­маль­ной про­тя­жен­но­сти в каж­дой схеме, ко­то­рый не пре­вы­ша­ет 5.

 

Ответ: 4.

Сергей Гетман 24.03.2016 18:10

На схеме 1 A-D-C (2+3=5)

Никита Горохов

Да, но нас ин­те­ре­су­ет длина са­мо­го длин­но­го пути, а это A-B-D-C с дли­ной 8.