Присоединиться

9–11 класс·средний уровень

Сколько путей из А в М не проходят через город Г

Условие

Дороги с односторонним движением связывают пункты А, Б, В, Г, Д, Е, Ж и М: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Е, Г→Ж, Д→Е, Д→Ж, Е→М, Ж→М. Сколько существует путей из А в М, которые НЕ проходят через пункт Г?

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

Решение по шагам

  1. Шаг 1. Два правила, на которых держится решение

    Задачи «через заданный пункт» и «мимо заданного пункта» решают одной парой приёмов:

    • правило умножения: любой путь через Г — это путь из А в Г, продолженный путём из Г в М, поэтому число путей через Г равно (число путей А→Г) ⋅\cdot (число путей Г→М);
    • правило вычитания: путей мимо Г ровно столько, сколько всего путей, минус пути через Г.

    Значит, план такой: посчитать все пути, потом пути через Г, потом вычесть.

  2. Шаг 2. Считаем общее число путей из А в М

    Обозначим N(X)N(X) — число путей из А в XX, и будем складывать значения предшественников. Порядок обработки: А, Б, В, Г, Д, Е, Ж, М — все дороги в нём ведут только вперёд.

    N(А)=1N(А)=1; N(Б)=1N(Б)=1; N(В)=1N(В)=1;

    N(Г)=N(Б)+N(В)=2N(Г)=N(Б)+N(В)=2; N(Д)=N(Б)+N(В)=2N(Д)=N(Б)+N(В)=2;

    N(Е)=N(Г)+N(Д)=4N(Е)=N(Г)+N(Д)=4; N(Ж)=N(Г)+N(Д)=4N(Ж)=N(Г)+N(Д)=4;

    N(М)=N(Е)+N(Ж)=4+4=8N(М)=N(Е)+N(Ж)=4+4=8. Всего 8 путей.

Осталось ещё 3 шага

  1. Шаг 3. Считаем пути через Г

  2. Шаг 4. Вычитаем и получаем ответ

  3. Шаг 5. Проверка другим способом

Получить полное решение

Бесплатно · займёт минуту

Частые ошибки

  • Вычитают из общего числа путей только количество путей из А в Г (то есть 2) и получают 6 — вычитать надо все пути, проходящие через Г, а их 2⋅2=42 \cdot 2 = 4.

  • Убирают вершину Г, но забывают убрать её дороги — и в пересчёте в Е и Ж по-прежнему «въезжают» через несуществующий пункт.

  • Считают, что «не проходит через Г» значит «не начинается и не кончается в Г», и отвечают 8.

  • Теряют дорогу Г→Ж, насчитывают только 2 пути через Г и получают 6 вместо 4.

Другие задачи по теме «Графы и таблицы»