Задача 1. Между населёнными пунктами Море, Лес, Холм, Река и Поляна построены велосипедные дороги. Их протяжённость в километрах приведена в таблице.
Реши задание на изображении
Сверь числа и знаки с фото.
Задача 1. Между населёнными пунктами Море, Лес, Холм, Река и Поляна построены велосипедные дороги. Их протяжённость в километрах приведена в таблице. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
Море Лес Холм Река Поляна Море — 4 3 12 15 Лес 4 — 8 4 6 Холм 3 8 — 4 2 Река 12 4 4 — 2 Поляна 15 6 2 2 — Вопросы:
- Выпишите из таблицы все дороги (рёбра). Сколько всего дорог построено между посёлками?
- Определите длину кратчайшего пути из пункта Море в пункт Река.
- Определите длину кратчайшего пути из пункта Море в пункт Поляна, который обязательно проходит через Холм.
- Какова длина кратчайшего пути между Морем и Поляной?
Задача 2. Между населёнными пунктами А, Б, В, Г, Д построены дороги. Их протяжённость в километрах приведена в таблице. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
А Б В Г Д А — 4 10 — 15 Б 4 — 2 6 — В 10 2 — 3 8 Г — 6 3 — 2 Д 15 — 8 2 — Вопросы:
- Выпишите из таблицы все дороги (рёбра). Сколько всего дорог построено между посёлками?
- Определите длину кратчайшего пути между пунктами А и Д.
- Определите длину кратчайшего пути между пунктами А и Г, проходящего через пункт В.
Задача 3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A B C D E F A — 3 5 15 B 3 — 1 4 C 5 1 — 2 9 D 4 2 — 3 6 E 3 — 2 F 15 9 6 2 — Вопросы:
- Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Кратко
- Задача 1: 1) всего 10 дорог; 2) 7 км; 3) 5 км; 4) 5 км.
- Задача 2: 1) всего 8 дорог; 2) 11 км; 3) 9 км.
- Задача 3: 11 км.
Как это получается
Задача 1
Таблица — это граф: пункты — вершины, дороги — рёбра. Каждая дорога записана дважды, поэтому считаем только один раз.
Все дороги:
Море—Лес \(4\); Море—Холм \(3\); Море—Река \(12\); Море—Поляна \(15\);
Лес—Холм \(8\); Лес—Река \(4\); Лес—Поляна \(6\);
Холм—Река \(4\); Холм—Поляна \(2\);
Река—Поляна \(2\).
Итого 10 дорог.
- Кратчайший путь Море → Река:
- Море → Холм → Река: \(3+4=7\) км;
- Море → Холм → Поляна → Река: \(3+2+2=7\) км;
- напрямую: \(12\) км.
Значит, 7 км.
- Путь Море → Поляна обязательно через Холм:
\[ 3+2=5 \]
То есть Море → Холм → Поляна, 5 км.
- Самый короткий путь Море → Поляна — тоже через Холм:
\[ 3+2=5 \]
Ответ: 5 км.
Задача 2
Все дороги:
А—Б \(4\); А—В \(10\); А—Д \(15\);
Б—В \(2\); Б—Г \(6\);
В—Г \(3\); В—Д \(8\);
Г—Д \(2\).
Итого 8 дорог.
- Кратчайший путь А → Д:
\[ \text{А → Б → В → Г → Д}=4+2+3+2=11 \]
Проверка: напрямую А—Д \(15\), через Б—Г—Д \(4+6+2=12\).
Значит, 11 км.
- Путь А → Г через В:
\[ \text{А → Б → В → Г}=4+2+3=9 \]
Ответ: 9 км.
Задача 3
Нужен путь A → F, проходящий через C. Кратчайший вариант:
\[ \text{A → B → C → D → E → F} \]
\[ 3+1+2+3+2=11 \]
Другие варианты длиннее, например A → C → D → E → F даёт \(5+2+3+2=12\).
Ответ: 11 км.
Общий принцип: в такой таблице ищи сумму весов рёбер вдоль маршрута; прямую дорогу выбирать не всегда выгодно, а для пути «через пункт» этот пункт обязательно включается в маршрут.
