Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3827730
А
Аноним
12 часов назад · публичный вопрос
А
Аноним

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.

Запрос пользователя

Реши задание на изображении

Ответ нейросети
12 часов назад

На фото несколько отдельных номеров; я решил все. Кратко:

Задание Ответ
26 9
27 5
28 9
29 12
16 5
17 3
18 5

Задания 26–29: подсчёт путей

Главный принцип: в направленном графе число путей до вершины равно сумме путей, приходящих в неё по входящим стрелкам. Если путь обязан проходить через фиксированную вершину, удобно считать отдельно: сколько путей дойти до неё и сколько путей пройти от неё до финиша, а затем перемножить.

  • 26. До города Ж ведут 3 варианта пути. От Ж до М без захода в К есть 3 варианта: через Л, через И и через И—Л.
    Значит, \(3\cdot3=9\).

  • 27. Выписываем все пути A → F:

    1. A—B—F
    2. A—C—G—F
    3. A—D—G—F
    4. A—E—G—F
    5. A—E—H—F
      Итого 5.
  • 28. До Е можно дойти 3 способами. После Е путь идёт через Ж, а от Ж до П есть 3 варианта: напрямую, через К и через Н.
    Получаем \(3\cdot3=9\).

  • 29. До Ж — 4 пути. От Ж до К — 3 варианта: напрямую, через И и через З.
    Тогда \(4\cdot3=12\).

Задания 16–18: кратчайший путь

  • 16. Путь A—B—C—D:
    \(3+1+1=5\).
    Прямая дорога A—D равна 6, поэтому она не минимальна. Ответ: 5.

  • 17. В таблице есть прямая дорога A—D длины 3, и более короткого пути по таблице нет. Ответ: 3.

  • 18. Путь A—B—C—D—E:
    \(2+1+1+1=5\).
    Через C—E тоже получается \(2+1+2=5\). Ответ: 5.