Ваш браузер устарел. Рекомендуем обновить его до последней версии.

Меню сайта


Счётчик посещений


 

счетчик посещений

 

Мысль дня

Часы

Календарь

Календари на любой год - Календарь.Юрец.Ру

Обратная связь

Поля, помеченные символом *, обязательны для заполнения.

5. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

  A B C D E F
A   3     29  
B 3   11 3 8  
C   11     4  
D   3     2  
E 29 8 4 2   7
F         7  

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Ответ 15

Решение:

Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.

 

 

 

 

 

 

 

 

 

 

A - B - C - E - F = 3 + 11 + 3 + 7 = 24

A - B - E - F = 3 + 8 + 7 =18

A - E - F = 29 + 7 = 36

A - B - D - E - F = 3 + 3 + 2 + 7 = 15

 

НАЗАД