Компания хочет сократить число вариантов доставки вдвое, закрыв одно направление.
Реши задание на изображении
Сверь числа и знаки с фото.
Закрыть одну дорогу Компания хочет сократить число вариантов доставки вдвое, закрыв одно направление. На схеме показаны дороги с односторонним движением между пунктами А, Б, В, Г, Д, Е и Ж. [Рисунок: ориентированный граф с вершинами А, Б, В, Г, Д, Е, Ж; стрелки: А → Б, А → В, Б → Г, Б → Д, В → Г, В → Д, Г → Ж, Г → Е, Д → Е, Д → Ж, Е → Ж] Сейчас из А в Ж ведут восемь маршрутов. Диспетчеру нужно, чтобы их осталось ровно четыре, и для этого он закроет одну дорогу. Отметь дорогу, которую нужно закрыть.
Сейчас из А в Ж ведут восемь маршрутов. Диспетчеру нужно, чтобы их осталось ровно четыре, и для этого он закроет одну дорогу. Отметь дорогу, которую нужно закрыть. ◉ Е → Ж ○ Г → Ж ○ Г → Е ○ Д → Ж Выбрали именно эту дорогу, потому что... Отметь все верные обоснования.
Выбрали именно эту дорогу, потому что... Отметь все верные обоснования. ☐ Дуга Е → Ж последняя на схеме, поэтому её закрытие всегда даёт наименьший результат ☐ После закрытия в Ж приходят только маршруты из Г и из Д: 2 + 2 = 4 ☐ Закрытие любой дороги уменьшает число маршрутов вдвое ☐ Вес Е равен 4, и все эти четыре маршрута заканчивались дугой Е → Ж ☐ В Ж ведут три дороги — из Г, из Д и из Е; закрыв одну из них, мы убираем ровно столько маршрутов, сколько весит её начало ☐ Если закрыть дорогу Г → Ж, маршрутов тоже станет четыре
Ответ: закрыть дорогу \(Е \to Ж\). Верные обоснования — 2-е, 4-е и 5-е.
Как считать маршруты
Каждой вершине дадим «вес» — число маршрутов из А в эту вершину. Идём по схеме слева направо и складываем веса всех вершин, откуда идёт стрелка:
- А = 1
- Б = 1 (только из А)
- В = 1 (только из А)
- Г = Б + В = 1 + 1 = 2
- Д = Б + В = 1 + 1 = 2
- Е = Г + Д = 2 + 2 = 4
- Ж = Г + Д + Е = 2 + 2 + 4 = 8
Получилось 8 — сходится с условием, значит схему прочитали верно.
Почему именно \(Е \to Ж\)
Если закрыть дорогу \(X \to Ж\), пропадут все маршруты, проходившие через неё, а их ровно столько, сколько путей ведёт из А в \(X\): дойдя до \(X\), каждый маршрут дальше шёл в Ж этой дорогой.
- \(Е \to Ж\): теряем 4 маршрута, остаётся \(8 - 4 = 4\) ✓
- \(Г \to Ж\): теряем 2, остаётся 6
- \(Д \to Ж\): теряем 2, остаётся 6
- \(Г \to Е\): теряем вес Г, то есть 2 (из Е дальше только \(Е \to Ж\)), остаётся 6
Проверка обоснований
- После закрытия \(Е \to Ж\) в Ж ведут только пути из Г (2 маршрута) и из Д (2 маршрута): \(2 + 2 = 4\) — верно.
- Вес Е равен 4, и все эти четыре маршрута заканчивались дугой \(Е \to Ж\) — верно.
- В Ж входят три дороги — из Г, Д и Е; закрывая дорогу, убираем столько маршрутов, сколько весит её начало (2, 2 и 4) — верно, поэтому выгодна именно дуга из Е.
- Неверно: важно не положение дуги на рисунке, а сколько маршрутов через неё идёт.
- Неверно: закрытие \(Г \to Ж\) убирает лишь 2 из 8 маршрутов.
- Неверно: после закрытия \(Г \to Ж\) останется 6 маршрутов.
Приём на будущее: в таких задачах не перебирай маршруты по одному — считай веса вершин, и тогда сразу видно, какая дорога «уносит» нужное число путей.
