Анализировать простейшие модели объектов · 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 | 2 | 3 | 7 | 15 | ||
B | 2 | 3 | ||||
C | 3 | 5 | ||||
D | 7 | 3 | 5 | 2 | 11 | |
E | 2 | 4 | ||||
F | 15 | 11 | 4 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение. Для поиска кратчайшего пути между пунктами A и F удобно использовать метод построения дерева возможных маршрутов или схематичного графа. Выпишем все возможные связи между пунктами, указанные в таблице:
A связан с: B (2 км), C (3 км), D (7 км), F (15 км).
B связан с: A (2 км), D (3 км).
C связан с: A (3 км), D (5 км).
D связан с: A (7 км), B (3 км), C (5 км), E (2 км), F (11 км).
E связан с: D (2 км), F (4 км).
F связан с: A (15 км), D (11 км), E (4 км).
Теперь рассмотрим все возможные пути из A в F, учитывая условие, что каждый пункт можно посетить только один раз:
1) Прямой путь: A → F
Длина: 15 км.
2) Пути через пункт D:
• A → D → F: 7+11=18 км.
• A → B → D → F: 2+3+11=16 км.
• A → C → D → F: 3+5+11=19 км.
3) Пути через пункт E (который связан с D и F):
• A → D → E → F: 7+2+4=13 км.
• A → B → D → E → F: 2+3+2+4=11 км.
• A → C → D → E → F: 3+5+2+4=14 км.
Сравним полученные результаты: 15, 18, 16, 19, 13, 11, 14.
Самым коротким является маршрут A → B → D → E → F, длина которого составляет 11 км.
Ответ: 11 км
Источник: ФИПИ