Анализировать простейшие модели объектов · 81 задание
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пункт…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A , B , C , D , E , F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайш…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | F | |
A | 3 | 5 | 15 | |||
B | 3 | 1 | ||||
C | 5 | 1 | 2 | |||
D | 2 | 4 | 6 | |||
E | 4 | 1 | ||||
F | 15 | 6 | 1 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение. Для нахождения кратчайшего пути между пунктами A и F воспользуемся методом построения дерева возможных путей, начиная из пункта A. Это позволит нам наглядно сравнить все варианты и выбрать самый короткий.
1. Из пункта A мы можем попасть в:
— B (длина 3 км)
— C (длина 5 км)
— F (длина 15 км) — это прямой путь, запомним его длину.
2. Рассмотрим продолжение пути из пункта B (уже пройдено 3 км):
— В C (длина 1 км). Итого путь A-B-C: 3+1=4 км.
— В A возвращаться нельзя по условию задачи.
3. Теперь рассмотрим пути из пункта C. Мы можем попасть в него напрямую из A (длина 5) или через B (длина 4). Выгоднее идти через B.
Из C (путь A-B-C, длина 4) можно пойти:
— В D (длина 2 км). Итого путь A-B-C-D: 4+2=6 км.
— В B и A возвращаться нельзя.
4. Рассмотрим продолжение пути из пункта D (путь A-B-C-D, длина 6):
— В E (длина 4 км). Итого путь A-B-C-D-E: 6+4=10 км.
— В F (длина 6 км). Итого путь A-B-C-D-F: 6+6=12 км.
5. Рассмотрим продолжение пути из пункта E (путь A-B-C-D-E, длина 10):
— В F (длина 1 км). Итого путь A-B-C-D-E-F: 10+1=11 км.
— В D возвращаться нельзя.
6. Сравним все найденные маршруты до пункта F:
— A-F: 15 км
— A-B-C-D-F: 12 км
— A-B-C-D-E-F: 11 км
Другие варианты (например, через прямую дорогу A-C) будут заведомо длиннее, так как путь A-C (5 км) длиннее, чем A-B-C (4 км).
Таким образом, кратчайший путь равен 11 км.
Ответ: 11
Источник: ФИПИ